Record link: 
http://hdl.handle.net/20.500.12708/188982
-
Title: 
Testing Upward Planarity of Partial 2-Trees
en
Citation: 
Chaplick, S., Di Giacomo, E., Frati, F., Ganian, R., Raftopoulou, C., & Simonov, K. (2022). Testing Upward Planarity of Partial 2-Trees. In P. Angelini & R. von Hanxleden (Eds.), Graph Drawing and Network Visualization. GD 2022 (pp. 175–187). Springer. https://doi.org/10.1007/978-3-031-22203-0_13
-
Publisher DOI: 
10.1007/978-3-031-22203-0_13
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Chaplick, Steven 
Di Giacomo, Emilio 
Frati, Fabrizio 
Ganian, Robert 
Raftopoulou, Chrysanthi 
Simonov, Kirill 
-
Organisational Unit: 
E192 - Institut für Logic and Computation 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Graph Drawing and Network Visualization. GD 2022 
-
ISBN: 
978-3-031-22203-0
-
Volume: 
13764
-
DOI of the book: 
10.1007/978-3-031-22203-0
-
Date (published): 
Sep-2022
-
Event name: 
International Symposium on Graph Drawing and Network Visualization (GD 2022) 
en
Event date: 
13-Sep-2022 - 16-Sep-2022
-
Event place: 
Tokyo, Japan
-
Number of Pages: 
13
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
Upward planarity
en
 
parameterized complexity; Exact Algorithms
-
Abstract: 
We present an O(n2)-time algorithm to test whether an n-vertex directed partial 2-tree is upward planar. This result improves upon the previously best known algorithm, which runs in O(n4) time.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

182
checked on Nov 23, 2023

Google ScholarTM

Check