The complexity of bendless three-dimensional orthogonal graph drawing

DOI10.7155/JGAA.00283zbMATH Open1260.05098DBLPjournals/jgaa/Eppstein13arXiv0709.4087OpenAlexW3105596242WikidataQ56390643 ScholiaQ56390643MaRDI QIDQ4910552FDOQ4910552

Authors: David Eppstein 

Publication date: 19 March 2013

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

Abstract: We consider embeddings of 3-regular graphs into 3-dimensional Cartesian coordinates, in such a way that two vertices are adjacent if and only if two of their three coordinates are equal (that is, if they lie on an axis-parallel line) and such that no three points lie on the same axis-parallel line; we call a graph with such an embedding an xyz graph}. We describe a correspondence between xyz graphs and face-colored embeddings of the graph onto two-dimensional manifolds, and we relate bipartiteness of the xyz graph to orientability of the underlying topological surface. Using this correspondence, we show that planar graphs are xyz graphs if and only if they are bipartite, cubic, and three-connected, and that it is NP-complete to determine whether an arbitrary graph is an xyz graph. We also describe an algorithm with running time O(n 2^{n/2}) for testing whether a given graph is an xyz graph.

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

Recommendations

• The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing
• Complexity results for three-dimensional orthogonal graph drawing
• Three-dimensional orthogonal graph drawing algorithms
• Three-dimensional graph drawing
• Graph Drawing

zbMATH Keywords

embeddings of 3-regular graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited In (13)

• Graph Drawing
• Complexity results for three-dimensional orthogonal graph drawing
• On the Hardness of Orthogonal-Order Preserving Graph Drawing
• Graph Drawing
• 1-bend 3-D orthogonal box-drawings: Two open problems solved
• Drawing Kn in Three Dimensions with One Bend per Edge
• Title not available (Why is that?)
• Upward planar drawings with two slopes
• Title not available (Why is that?)
• The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing
• Three-Dimensional 1-Bend Graph Drawings
• Optimal Orthogonal Graph Drawing with Convex Bend Costs
• Graph Drawing

This page was built for publication: The complexity of bendless three-dimensional orthogonal graph drawing

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