Simultaneous visibility representations of plane st-graphs using L-shapes

DOI10.1016/J.TCS.2016.06.045MaRDI QIDQ306259zbMATHOpenAlexFDO

Authors W. Evans, Giuseppe Liotta, Fabrizio Montecchiani

Publication date 31 August 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.04388

zbMATH Keywords

simultaneous RAC embeddingsimultaneous visibility representations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Let $langle{G}_r,G_{b}angle$ be a pair of plane $st$-graphs with the same vertex set $V$. A simultaneous visibility representation with L-shapes of $langle{G}_r,G_{b}angle$ is a pair of bar visibility representations $langleGamm{a}_r,Gamm{a}_{b}angle$ such that, for every vertex $vinV$, $Gamm{a}_r(v)$ and $Gamm{a}_b(v)$ are a horizontal and a vertical segment, which share an end-point. In other words, every vertex is drawn as an $L$-shape, every edge of $G_r$ is a vertical visibility segment, and every edge of $G_b$ is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: (i) a characterization of those pairs of plane $st$-graphs admitting such a representation, (ii) a cubic time algorithm to recognize them, and (iii) a linear time drawing algorithm if the test is positive.

Recommendations

• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• Simultaneous visibility representations of undirected pairs of graphs
• Simultaneous drawing of planar graphs with right-angle crossings and few bends
• Simultaneous drawing of planar graphs with right-angle crossings and few bends
• Visibility representation of plane graphs with simultaneous bound for both width and height

Cites work

• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 1962799 (Why is no real title available?)
• A unified approach to visibility representations of planar graphs
• Geometric RAC simultaneous drawings of graphs
• Geometric simultaneous embeddings of a graph and a matching
• On a tree and a path with no geometric simultaneous embedding
• On simultaneous planar graph embeddings
• Rectangle and Square Representations of Planar Graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Simultaneous drawing of planar graphs with right-angle crossings and few bends
• Simultaneous interval graphs
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• The crossing-angle resolution in graph drawing
• The simultaneous representation problem for chordal, comparability and permutation graphs
• Transversal structures on triangulations: A combinatorial study and straight-line drawings

Cited in

(8)

• The QuaSEFE problem
• Simultaneous visibility representations of undirected pairs of graphs
• Optimal-area visibility representations of outer-1-plane graphs
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• An annotated bibliography on 1-planarity
• Edge Partitions and Visibility Representations of 1-planar Graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Combinatorial properties and recognition of unit square visibility graphs

This page was built for publication: Simultaneous visibility representations of plane \(st\)-graphs using L-shapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306259)