Upward planarity testing: A computational study

DC FieldValueLanguage
dc.contributor.authorChimani, M.
dc.contributor.authorZeranski, R.
dc.date.accessioned2021-12-23T16:30:42Z-
dc.date.available2021-12-23T16:30:42Z-
dc.date.issued2013
dc.identifier.isbn9783319038407
dc.identifier.issn03029743
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/16707-
dc.descriptionConference of 21st International Symposium on Graph Drawing, GD 2013 ; Conference Date: 23 September 2013 Through 25 September 2013; Conference Code:101897
dc.description.abstractA 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.
dc.description.sponsorshipet al.; Microsoft; Region Aquitaine; Tom Sawyer Software; Vis4; y Works
dc.language.isoen
dc.publisherSpringer Verlag
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectBranch and bound method
dc.subjectDrawing (graphics), Algorithmic approach
dc.subjectBranch-and-bound algorithms
dc.subjectComputational studies
dc.subjectDirected acyclic graph (DAG)
dc.subjectExperimental comparison
dc.subjectNP Complete
dc.subjectPlanarity
dc.subjectTheoretical points, Directed graphs
dc.titleUpward planarity testing: A computational study
dc.typeconference paper
dc.identifier.doi10.1007/978-3-319-03841-4_2
dc.identifier.scopus2-s2.0-84891840329
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84891840329&doi=10.1007%2f978-3-319-03841-4_2&partnerID=40&md5=64ab06436af409ef71f598d6bc94eac3
dc.description.volume8242 LNCS
dc.description.startpage13
dc.description.endpage24
dc.publisher.placeBordeaux
dcterms.isPartOf.abbreviationLect. Notes Comput. Sci.
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

3
Last Week
0
Last month
0
checked on May 27, 2024

Google ScholarTM

Check

Altmetric