Upward planarity testing: A computational study

Autor(en): Chimani, M. 
Zeranski, R.
Stichwörter: Branch and bound method; Drawing (graphics), Algorithmic approach; Branch-and-bound algorithms; Computational studies; Directed acyclic graph (DAG); Experimental comparison; NP Complete; Planarity; Theoretical points, Directed graphs
Erscheinungsdatum: 2013
Herausgeber: Springer Verlag
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen: 8242 LNCS
Startseite: 13
Seitenende: 24
Zusammenfassung: 
A directed acyclic graph (DAG) is upward planar if it can be drawn without any crossings while all edges - when following them in their direction - are drawn with strictly monotonously increasing y-coordinates. Testing whether a graph allows such a drawing is known to be NP-complete, but there is a substantial collection of different algorithmic approaches known in literature. In this paper, we give an overview of the known algorithms, ranging from combinatorial FPT and branch-and-bound algorithms to ILP and SAT formulations. Most approaches of the first class have only been considered from the theoretical point of view, but have never been implemented. For the first time, we give an extensive experimental comparison between virtually all known approaches to the problem. Furthermore, we present a new SAT formulation based on a recent theoretical result by Fulek et al. [8], which turns out to perform best among all known algorithms. © 2013 Springer International Publishing Switzerland.
Beschreibung: 
Conference of 21st International Symposium on Graph Drawing, GD 2013 ; Conference Date: 23 September 2013 Through 25 September 2013; Conference Code:101897
ISBN: 9783319038407
ISSN: 03029743
DOI: 10.1007/978-3-319-03841-4_2
Externe URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-84891840329&doi=10.1007%2f978-3-319-03841-4_2&partnerID=40&md5=64ab06436af409ef71f598d6bc94eac3

Show full item record

Page view(s)

2
Last Week
0
Last month
1
checked on Apr 24, 2024

Google ScholarTM

Check

Altmetric