Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102320
Title: Contact representations of graphs in 3D
Authors: Alam, J.
Evans, W.
Kobourov, S.
Pupyrev, S.
Toeniskoetter, J.
Ueckerdt, T.
Issue Date: 2015
Publisher: Springer Verlag
Citation: Contact representations of graphs in 3D / J. Alam, W. Evans, S. Kobourov, et al. — DOI 10.1007/978-3-319-21840-3_2 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 9214. — P. 14-27.
Abstract: We study contact representations of non-planar 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 present a liner-time algorithm constructing a representation of a 3-connected planar graph, its dual, and the vertex-face incidence graph with 3D boxes. We then investigate contact representations of 1- planar graphs. We first prove that optimal 1-planar graphs without separating 4-cycles admit a contact representation with 3D boxes. However, since not every optimal 1-planar graph can be represented in this way, we also 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 graphs with L-shapes. © Springer International Publishing Switzerland 2015.
Keywords: ALGORITHMS
DATA STRUCTURES
GEOMETRY
GRAPHIC METHODS
1-PLANAR GRAPHS
3-CONNECTED PLANAR GRAPHS
3D OBJECT
INCIDENCE GRAPHS
NON-PLANAR GRAPHS
QUADRATIC TIME ALGORITHMS
REPRESENTATIONS OF GRAPHS
TIME ALGORITHMS
GRAPH THEORY
URI: http://hdl.handle.net/10995/102320
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84951816003
PURE ID: 570052
be24f858-16ed-43b3-8ef2-8dc4986c25aa
ISSN: 3029743
ISBN: 9783319218397
DOI: 10.1007/978-3-319-21840-3_2
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84951816003.pdf591,14 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.