Abstract
Let G be a graph embedded in the plane and let A be an arrangement of pseudolines intersecting the drawing of G. An aligned drawing of G and A is a planar polyline drawing Γ of G with an arrangement A of lines so that Γ and A are homeomorphic to G and A We show that if A is stretchable and every edge e either entirely lies on a pseudoline or intersects at most one pseudoline, then G and A have a straight-line aligned drawing. In order to prove these results, we strengthen the result of Da Lozzo et al. [5], and prove that a planar graph G and a single pseudoline L have an aligned drawing with a prescribed convex drawing of the outer face. We also study the more general version of the problem where only a set of vertices is given and we need to determine whether they can be collinear. We show that the problem is NP hard but fixed-parameter tractable.
| Original language | English |
|---|---|
| Title of host publication | Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers |
| Editors | F. Frati, K.-L. Ma |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 3-16 |
| Number of pages | 14 |
| ISBN (Print) | 9783319739144 |
| DOIs | |
| Publication status | Published - 2018 |
| Event | 25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, United States Duration: 25 Sept 2017 → 27 Sept 2017 Conference number: 25 https://gd2017.ccis.northeastern.edu/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 10692 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 25th International Symposium on Graph Drawing and Network Visualization (GD 2017) |
|---|---|
| Abbreviated title | GD 2017 |
| Country/Territory | United States |
| City | Boston |
| Period | 25/09/17 → 27/09/17 |
| Internet address |
Funding
Work was partially supported by grant WA 654/21-1 of the German Research Foundation (DFG).