2-layer fan-planarity: From caterpillar to stegosaurus

Autor(en): Binucci, C.
Chimani, M. 
Didimo, W.
Gronemann, M.
Klein, K.
Kratochvìl, J.
Montecchiani, F.
Tollis, I.G.
Herausgeber: Di Giacomo, E.
Lubiw, A.
Stichwörter: Drawing (graphics); Visualization, Different layers; Embedding algorithms; Horizontal layers; Independent edges; Linear time; Planar drawing; Planar graph; Straight-line segments, Graphic methods
Erscheinungsdatum: 2015
Herausgeber: Springer Verlag
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen: 9411
Startseite: 281
Seitenende: 294
In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are assigned to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs. © Springer International Publishing Switzerland 2015.
Conference of 23rd International Symposium on Graph Drawing and Network Visualization, GD 2015 ; Conference Date: 24 September 2015 Through 26 September 2015; Conference Code:159389
ISBN: 9783319272603
ISSN: 03029743
DOI: 10.1007/978-3-319-27261-0_24
Externe URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-84952020275&doi=10.1007%2f978-3-319-27261-0_24&partnerID=40&md5=1049eb5dd1742fd2871f3ef3b5ee8afe

Show full item record

Page view(s)

Last Week
Last month
checked on Apr 24, 2024

Google ScholarTM