Simultaneous graph embedding with bends and circular arcs

Justin Cappos, Alejandro Estrella-Balderrama, J. Joseph Fowler, Stephen G. Kobourov

    Research output: Contribution to journalArticle

    Abstract

    A simultaneous embedding of two vertex-labeled planar graphs on n vertices is possible if there exists a labeled point set of size n such that each of the graphs can be realized on that point set without crossings. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph. We also show how to use star-shaped levels to find 2-bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in O(n) time.

    Original languageEnglish (US)
    Pages (from-to)173-182
    Number of pages10
    JournalComputational Geometry: Theory and Applications
    Volume42
    Issue number2
    DOIs
    StatePublished - Feb 2009

    Keywords

    • Simultaneous embedding

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Simultaneous graph embedding with bends and circular arcs'. Together they form a unique fingerprint.

  • Cite this