Contact representations of graphs in 3D

DOI10.1007/978-3-319-21840-3_2MaRDI QIDQ3449802zbMATH OpenOpenAlexFDO

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

Publication date 30 October 2015

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3308932 (Why is no real title available?)
• 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
• Combinatorial and geometric properties of planar Laman graphs
• Contact representations of graphs in 3D
• Contact representations of planar graphs with cubes
• Ein Sechsfarbenproblem auf der Kugel
• Generation of simple quadrangulations of the sphere
• Interval representations of planar graphs
• More canonical ordering
• On representing graphs by touching cuboids
• On the number of mutually touching cylinders
• Re-embeddings of Maximum 1-Planar Graphs
• Rectangular layouts and contact graphs
• Remez-type inequality for discrete sets
• Representations by contact and intersection of segments
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Schnyder decompositions for regular plane graphs and application to drawing
• Schnyder woods and orthogonal surfaces
• The structure of 1-planar graphs
• Triangle contact representations and duality
• Zur Struktur 1‐planarer Graphen

Cited in

(16)

• Side-contact representations with convex polygons in 3D: new results for complete bipartite graphs
• Contact representations of graphs in 3D
• Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
• Pixel and voxel representations of graphs
• Unit contact representations of grid subgraphs with regular polytopes in 2D and 3D
• On Triangle Contact Graphs
• Representing graphs and hypergraphs by touching polygons in 3D
• Equilateral L-contact graphs
• Contact representations of directed planar graphs in 2D and 3D
• Contact representations of planar graphs with cubes
• An annotated bibliography on 1-planarity
• On balanced +-contact representations
• Structural parameters of Schnyder woods
• On partitioning the edges of 1-plane graphs
• Schnyder Woods and long induced paths in 3-connected planar graphs
• On representing graphs by touching cuboids

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)