1-visibility representations of 1-planar graphs

DOI10.7155/JGAA.00330MaRDI QIDQ2921090zbMATH OpenOpenAlexFDO

Authors Franz J. Brandenburg

Publication date 30 September 2014

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

linear time algorithm1-visible graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A visibility representation is a classical drawing style of planar graphs. It displays the vertices of a graph as horizontal vertex-segments, and each edge is represented by a vertical edge-segment touching the segments of its end vertices; beyond that segments do not intersect. We generalize visibility to 1-visibility, where each edge- (vertex-) segment crosses at most one vertex- (edge-) segment. In other words, a vertex is crossed by at most one edge, and vice-versa. We show that 1-visibility properly extends 1-planarity and develop a linear time algorithm to compute a 1-visibility representation of an embedded 1-planar graph on O(n^2) area. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. Concerning density, both 1-visible and 1-planar graphs of size $n$ have at most 4n-8 edges. However, for every n >= 7 there are 1-visible graphs with 4n-8 edge which are not 1-planar.

Recommendations

• 3D Visibility Representations of 1-planar Graphs
• Bar 1-visibility graphs and their relation to other nearly planar graphs
• \(\mathsf{T}\)-shape visibility representations of 1-planar graphs
• On visibility representations of non-planar graphs
• Thickness of Bar 1-Visibility Graphs

Cited in

(19)

• Embedding-preserving rectangle visibility representations of nonplanar graphs
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
• On visibility representations of non-planar graphs
• Straight-line drawings of 1-planar graphs
• L-visibility drawings of IC-planar graphs
• Edge Partitions and Visibility Representations of 1-planar Graphs
• On aligned bar 1-visibility graphs
• 3D Visibility Representations of 1-planar Graphs
• Optimal-area visibility representations of outer-1-plane graphs
• On 3D visibility representations of graphs with few crossings per edge
• On the density of non-simple 3-planar graphs
• Bar 1-visibility graphs and their relation to other nearly planar graphs
• An annotated bibliography on 1-planarity
• Optimal-area visibility representations of outer-1-plane graphs
• \(\mathsf{T}\)-shape visibility representations of 1-planar graphs
• 1-planarity testing and embedding: an experimental study
• On Aligned Bar 1-Visibility Graphs
• Colored anchored visibility representations in 2D and 3D space

This page was built for publication: 1-visibility representations of 1-planar graphs

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