Fixed-parameter tractable algorithms for testing upward planarity

Patrick Healy, Karol Lynch

Research output: Contribution to journalConference articlepeer-review

Abstract

We consider the problem of testing a digraph G = (V, E) for upward planarity. In particular we present two fixed-parameter tractable algorithms for testing the upward planarity of G. Let n -|V|, let t be the number of triconnected components of G, and let c be the number of cut-vertices of G. The first upward planarity testing algorithm we present runs in O(2t · t! · n2)-time. The previously known best result is an O(t! · 8t · n3 + 23.2c · t3.2c · t! · 8t · n)-time algorithm by Chan. We use the kernelisation technique to develop a second upward planarity testing algorithm which runs in O(n2 + K 4(2k +1)!) time, where k = |E| - |V|. We also define a class of non upward planar digraphs.

Original languageEnglish
Pages (from-to)199-208
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3381
DOIs
Publication statusPublished - 2005
Event31st Conference on Current Trends in Theory and Practice of Computer Science - Liptovsky Jan, Slovakia
Duration: 22 Jan 200528 Jan 2005

Fingerprint

Dive into the research topics of 'Fixed-parameter tractable algorithms for testing upward planarity'. Together they form a unique fingerprint.

Cite this