Contact representations of graphs in 3D

DOI10.1007/978-3-319-21840-3_2zbMATH Open1444.68130arXiv1501.00304OpenAlexW2963519387MaRDI QIDQ3449802FDOQ3449802

Jawaherul Alam M.D., Stephen G. Kobourov, Torsten Ueckerdt, W. Evans, Jackson Toeniskoetter, Sergey Pupyrev

Publication date: 30 October 2015

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

Abstract: We study contact representations of graphs in which vertices are represented by axis-aligned polyhedra in 3D and edges are realized by non-zero area common boundaries between corresponding polyhedra. We show that for every 3-connected planar graph, there exists a simultaneous representation of the graph and its dual with 3D boxes. We give a linear-time algorithm for constructing such a representation. This result extends the existing primal-dual contact representations of planar graphs in 2D using circles and triangles. While contact graphs in 2D directly correspond to planar graphs, we next study representations of non-planar graphs in 3D. In particular we consider representations of optimal 1-planar graphs. A graph is 1-planar if there exists a drawing in the plane where each edge is crossed at most once, and an optimal n-vertex 1-planar graph has the maximum (4n - 8) number of edges. We describe a linear-time algorithm for representing optimal 1-planar graphs without separating 4-cycles with 3D boxes. However, not every optimal 1-planar graph admits a representation with boxes. Hence, we consider contact representations with the next simplest axis-aligned 3D object, L-shaped polyhedra. We provide a quadratic-time algorithm for representing optimal 1-planar graph with L-shaped polyhedra.

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

Recommendations

• On Contact Graphs with Cubes and Proportional Boxes
• On representing graphs by touching cuboids
• Contact representations of planar graphs with cubes
• Contact representations of directed planar graphs in 2D and 3D
• Proportional Contact Representations of Planar Graphs

zbMATH Keywords

linear-time algorithmnon-planar graphsquadratic-time algorithmcontact representationsL-shaped polyhedra

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Ein Sechsfarbenproblem auf der Kugel
• Combinatorial and Geometric Properties of Planar Laman Graphs
• The structure of 1-planar graphs
• Representations by contact and intersection of segments
• Interval representations of planar graphs
• Generation of simple quadrangulations of the sphere
• Title not available (Why is that?)
• Schnyder woods and orthogonal surfaces
• Remez-type inequality for discrete sets
• On Representing Graphs by Touching Cuboids
• Contact representations of planar graphs with cubes
• Rectangular layouts and contact graphs
• Re-embeddings of Maximum 1-Planar Graphs
• Zur Struktur 1‐planarer Graphen
• Schnyder decompositions for regular plane graphs and application to drawing
• Triangle contact representations and duality
• Contact Representations of Graphs in 3D
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments
• Circle packings of maps in polynomial time
• More Canonical Ordering
• On the number of mutually touching cylinders

Cited In (9)

• Side-contact representations with convex polygons in 3D: new results for complete bipartite graphs
• Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
• Contact Representations of Graphs in 3D
• On Triangle Contact Graphs
• Representing graphs and hypergraphs by touching polygons in 3D
• Structural parameters of Schnyder woods
• An annotated bibliography on 1-planarity
• On partitioning the edges of 1-plane graphs
• Schnyder Woods and long induced paths in 3-connected planar graphs

This page was built for publication: Contact representations of graphs in 3D

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