T-shape visibility representations of 1-planar graphs
From MaRDI portal
Publication:1702255
DOI10.1016/J.COMGEO.2017.10.007zbMATH Open1381.05048arXiv1702.05265OpenAlexW2594460933MaRDI QIDQ1702255FDOQ1702255
Authors: Franz J. Brandenburg 
Publication date: 28 February 2018
Published in: Computational Geometry (Search for Journal in Brave)
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 . 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.
Full work available at URL: https://arxiv.org/abs/1702.05265
Recommendations
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- A new proof of the 6 color theorem
- Ein Sechsfarbenproblem auf der Kugel
- How to draw a planar graph on a grid
- A unified approach to visibility representations of planar graphs
- Rectilinear planar layouts and bipolar orientations of planar graphs
- Some results on visibility graphs
- Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
- Right angle crossing graphs and 1-planarity
- Straight-line grid drawings of 3-connected 1-planar graphs
- Title not available (Why is that?)
- Rectilinear drawings of graphs
- Title not available (Why is that?)
- On-Line Planarity Testing
- On the density of maximal 1-planar graphs
- 1-planarity of graphs with a rotation system
- Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
- The structure of plane graphs with independent crossings and its applications to coloring problems
- Algorithms for graphs embeddable with few crossings per edge
- Recognizing and drawing IC-planar graphs
- Coloring plane graphs with independent crossings
- Chromatic number, independence ratio, and crossing number
- Drawing graphs with right angle crossings
- Drawing planar graphs using the canonical ordering
- Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
- Computing an st-numbering
- Re-embeddings of Maximum 1-Planar Graphs
- Zur Struktur 1‐planarer Graphen
- Representing a planar graph by vertical lines joining different levels
- Bar k-Visibility Graphs
- Parameters of Bar k-Visibility Graphs
- On visibility representations of non-planar graphs
- Über 1-optimale Graphen
- On representations of some thickness-two graphs
- An annotated bibliography on 1-planarity
- 1-visibility representations of 1-planar graphs
- Bar 1-visibility graphs and their relation to other nearly planar graphs
- Ortho-polygon visibility representations of embedded graphs
- L-visibility drawings of IC-planar graphs
- An algorithm for straight-line drawing of planar graphs
- More canonical ordering
- \(\mathsf{NIC}\)-planar graphs
- Recognizing hole-free 4-map graphs in cubic time
- On bar \((1, j)\)-visibility graphs (extended abstract)
Cited In (9)
- Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
- Fan-crossing free graphs and their relationship to other beyond-planar graphs
- Straight-line drawings of 1-planar graphs
- Edge Partitions and Visibility Representations of 1-planar Graphs
- L-visibility drawings of IC-planar graphs
- Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
- Optimal-area visibility representations of outer-1-plane graphs
- Ortho-polygon visibility representations of 3-connected 1-plane graphs
- 1-visibility representations 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)
