Ortho-polygon visibility representations of embedded graphs

DOI10.1007/s00453-017-0324-2zbMath1392.68323arXiv1604.08797OpenAlexW2618797127MaRDI QIDQ724238

Walter Didimo, Fabrizio Montecchiani, Stephen K. Wismath, Emilio Di Giacomo, Giuseppe Liotta, Henk G. Meijer, William S. Evans

Publication date: 25 July 2018

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

non-planar graphs1-planarityorthogonal polygonsvisibility representationstesting and drawing algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Visibility representations of boxes in 2.5 dimensions ⋮ Optimal-area visibility representations of outer-1-plane graphs ⋮ An annotated bibliography on 1-planarity ⋮ Combinatorial properties and recognition of unit square visibility graphs ⋮ Area, perimeter, height, and width of rectangle visibility graphs ⋮ New results on edge partitions of 1-plane graphs ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ 3D Visibility Representations of 1-planar Graphs ⋮ Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles ⋮ Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles ⋮ Simultaneous visibility representations of undirected pairs of graphs ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ Edge partitions of optimal 2-plane and 3-plane graphs ⋮ Ortho-polygon visibility representations of 3-connected 1-plane graphs ⋮ Unnamed Item ⋮ On 3D visibility representations of graphs with few crossings per edge ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ 1-planarity testing and embedding: an experimental study ⋮ IC-Planar Graphs Are 6-Choosable

Uses Software

• GDToolkit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Area requirement of visibility representations of trees
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• On drawings and decompositions of 1-planar graphs
• A note on 1-planar graphs
• On partitioning the edges of 1-plane graphs
• L-visibility drawings of IC-planar graphs
• Finding a feasible flow in a strongly connected network
• Representing a planar graph by vertical lines joining different levels
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Rectangle-visibility representations of bipartite graphs
• Triangulating planar graphs while minimizing the maximum degree
• Right angle crossing graphs and 1-planarity
• On representations of some thickness-two graphs
• On RAC drawings of 1-planar graphs
• An annotated bibliography on 1-planarity
• Orthogonal Layout with Optimal Face Complexity
• Parameterized Complexity of 1-Planarity
• Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
• 1-Visibility Representations of 1-Planar Graphs
• Bar 1-Visibility Graphs and their relation to other Nearly Planar Graphs
• Re-embeddings of Maximum 1-Planar Graphs
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Computing orthogonal drawings with the minimum number of bends
• On-Line Planarity Testing
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• Accelerated Bend Minimization