Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/102320
Название: Contact representations of graphs in 3D
Авторы: Alam, J.
Evans, W.
Kobourov, S.
Pupyrev, S.
Toeniskoetter, J.
Ueckerdt, T.
Дата публикации: 2015
Издатель: Springer Verlag
Библиографическое описание: 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.
Аннотация: 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.
Ключевые слова: 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://elar.urfu.ru/handle/10995/102320
Условия доступа: info:eu-repo/semantics/openAccess
Идентификатор SCOPUS: 84951816003
Идентификатор PURE: 570052
be24f858-16ed-43b3-8ef2-8dc4986c25aa
ISSN: 3029743
ISBN: 9783319218397
DOI: 10.1007/978-3-319-21840-3_2
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-84951816003.pdf591,14 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.