Upward planarity testing in practice: SAT formulations and comparative study

DC FieldValueLanguage
dc.contributor.authorChimani, M.
dc.contributor.authorZeranski, R.
dc.date.accessioned2021-12-23T16:32:24Z-
dc.date.available2021-12-23T16:32:24Z-
dc.date.issued2015
dc.identifier.issn10846654
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17332-
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, and while the problem is polynomial-time solvable for special graph classes, there is not much known about solving the problem for general graphs in practice. The only attempt so far has been a branch-and-bound algorithm over the graph's triconnectivity structure, which was able to solve small graphs. Furthermore, there are some known FPT algorithms to deal with the problem. In this article, we propose two fundamentally different approaches based on the seemingly novel concept of ordered embeddings and on the concept of a Hanani-Tutte-type characterization of monotone drawings. In both approaches, we model the problem as special SAT instances, that is, logic formulae for which we check satisfiability. Solving these SAT instances allows us to decide upward planarity for arbitrary graphs. For the first time, we give an extensive experimental comparison between virtually all known approaches to the problem. To this end, we also investigate implementation issues and different variants of the known algorithms as well as of our SAT approaches and evaluate all algorithms on real-world as well as on constructed instances.We also give a detailed performance study of the novel SAT approaches.We show that the SAT formulations outperform all known approaches for graphs with up to 400 edges. For even larger graphs, a modified branch-and-bound algorithm becomes competitive. © Versita Sp. z o.o.
dc.language.isoen
dc.publisherAssociation for Computing Machinery
dc.relation.ispartofACM Journal of Experimental Algorithmics
dc.subjectCombinatorial algorithms
dc.subjectExperimental evaluation
dc.subjectGraph drawing
dc.subjectImplementations
dc.subjectSAT formulation
dc.subjectUpward planarity
dc.titleUpward planarity testing in practice: SAT formulations and comparative study
dc.typejournal article
dc.identifier.doi10.1145/2699875
dc.identifier.scopus2-s2.0-84928882333
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84928882333&doi=10.1145%2f2699875&partnerID=40&md5=8df5207ade5d907d44417ba953a6ea3b
dc.description.volume20
dc.description.issue1
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

6
Last Week
0
Last month
2
checked on May 27, 2024

Google ScholarTM

Check

Altmetric