T-shape visibility representations of 1-planar graphs

DOI10.1016/J.COMGEO.2017.10.007MaRDI QIDQ1702255zbMATH OpenOpenAlexFDO

Authors Franz J. Brandenburg

Publication date 28 February 2018

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

graph drawingorthogonal polygonsvisibility representationsbeyond-planar graphs

Mathematics Subject Classification ID

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

Abstract: A shape visibility representation displays a graph so that each vertex is represented by an orthogonal polygon of a particular shape and for each edge there is a horizontal or vertical line of sight between the polygons assigned to its endvertices. Special shapes are rectangles, L, T, E and H-shapes, and caterpillars. A flat rectangle is a horizontal bar of height $epsilon>0$. A graph is 1-planar if there is a drawing in the plane such that each edge is crossed at most once and is IC-planar if in addition no two crossing edges share a vertex. We show that every IC-planar graph has a flat rectangle visibility representation and that every 1-planar graph has a T-shape visibility representation. The representations use quadratic area and can be computed in linear time from a given embedding.

Recommendations

• 1-visibility representations of 1-planar graphs
• L-visibility drawings of IC-planar graphs
• 3D Visibility Representations of 1-planar Graphs
• On visibility representations of non-planar graphs
• Embedding-preserving rectangle visibility representations of nonplanar graphs

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• 1-planarity of graphs with a rotation system
• 1-visibility representations of 1-planar graphs
• A new proof of the 6 color theorem
• A unified approach to visibility representations of planar graphs
• Algorithms for graphs embeddable with few crossings per edge
• An algorithm for straight-line drawing of planar graphs
• An annotated bibliography on 1-planarity
• Bar 1-visibility graphs and their relation to other nearly planar graphs
• Bar k-Visibility Graphs
• Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
• Chromatic number, independence ratio, and crossing number
• Coloring plane graphs with independent crossings
• Computing an st-numbering
• Drawing graphs with right angle crossings
• Drawing planar graphs using the canonical ordering
• Ein Sechsfarbenproblem auf der Kugel
• How to draw a planar graph on a grid
• L-visibility drawings of IC-planar graphs
• More canonical ordering
• On bar \((1, j)\)-visibility graphs (extended abstract)
• On representations of some thickness-two graphs
• On the density of maximal 1-planar graphs
• On visibility representations of non-planar graphs
• On-Line Planarity Testing
• Parameters of Bar k-Visibility Graphs
• Re-embeddings of Maximum 1-Planar Graphs
• Recognizing hole-free 4-map graphs in cubic time
• Rectilinear drawings of graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Representing a planar graph by vertical lines joining different levels
• Right angle crossing graphs and 1-planarity
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Some results on visibility graphs
• Straight-line grid drawings of 3-connected 1-planar graphs
• The structure of plane graphs with independent crossings and its applications to coloring problems
• Zur Struktur 1‐planarer Graphen
• \(\mathsf{NIC}\)-planar graphs
• Über 1-optimale Graphen

Cited in

(8)

• 1-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
• Optimal-area visibility representations of outer-1-plane graphs
• Edge Partitions and Visibility Representations of 1-planar Graphs
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• L-visibility drawings of IC-planar graphs
• Straight-line drawings of 1-planar graphs

This page was built for publication: \(\mathsf{T}\)-shape 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 Q1702255)