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

DOI10.1016/J.TCS.2016.06.045zbMATH Open1348.68174arXiv1505.04388OpenAlexW2950599253MaRDI QIDQ306259FDOQ306259

Giuseppe Liotta, Fabrizio Montecchiani, W. Evans

Publication date: 31 August 2016

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

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.

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

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

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)

Cites Work

• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Crossing-Angle Resolution in Graph Drawing
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Simultaneous drawing of planar graphs with right-angle crossings and few bends
• Simultaneous Visibility Representations of Plane st-graphs Using L-shapes
• Rectangle and Square Representations of Planar Graphs
• Simultaneous Interval Graphs
• On a Tree and a Path with no Geometric Simultaneous Embedding
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• Title not available (Why is that?)
• Geometric RAC Simultaneous Drawings of Graphs
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
• Geometric Simultaneous Embeddings of a Graph and a Matching
• On simultaneous planar graph embeddings

Cited In (9)

• Simultaneous visibility representations of undirected pairs of graphs
• Title not available (Why is that?)
• Ortho-polygon visibility representations of embedded graphs
• Edge Partitions and Visibility Representations of 1-planar Graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Optimal-area visibility representations of outer-1-plane graphs
• Ortho-polygon visibility representations of 3-connected 1-plane graphs
• An annotated bibliography on 1-planarity
• The QuaSEFE problem

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)