Search Results

Documents authored by Biedl, Therese

Document
DOI: 10.4230/LIPIcs.GD.2024.10
Constrained Outer-String Representations

Authors: Therese Biedl, Sabine Cornelsen, Jan Kratochvíl, and Ignaz Rutter

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
An outer-string representation of a graph is an intersection representation in which each vertex is represented by a curve that is contained in the unit disk and has at least one endpoint on the boundary of the unit disk. In an outer-1-string representation the curves representing any two vertices are in addition allowed to intersect at most once. In this paper, we consider the following constrained version: Given a graph G plus a cyclic order v_1,…,v_n of the vertices in G, test whether G has an outer-string or an outer-1-string representation in which the curves representing v_1,…,v_n intersect the boundary of the unit disk in this order. We first show that a graph has an outer-string representation for all possible cyclic orders of the vertices if and only if the graph is the complement of a chordal graph. Then we turn towards the situation where one particular cyclic order of the vertices is fixed. We characterize the chordal graphs admitting a constrained outer-string representation and the trees and cycles admitting a constrained outer-1-string representation. The characterizations yield polynomial-time recognition and construction algorithms; in the case of outer-1-string representations the run time is linear. We also show how to decide in polynomial time whether an arbitrary graph admits a constrained L-shaped outer-1-string representation. In an L-shaped representation the curves are 1-bend orthogonal polylines anchored on a horizontal line, and they are contained in the half-plane below that line. However, not even all paths with a constrained outer-1-string representation admit one with L-shapes. We show that 2-bend orthogonal polylines are sufficient for trees and cycles with a constrained outer-1-string representation.
Cite as

Therese Biedl, Sabine Cornelsen, Jan Kratochvíl, and Ignaz Rutter. Constrained Outer-String Representations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.GD.2024.10,
  author =	{Biedl, Therese and Cornelsen, Sabine and Kratochv{\'\i}l, Jan and Rutter, Ignaz},
  title =	{{Constrained Outer-String Representations}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.10},
  URN =		{urn:nbn:de:0030-drops-212942},
  doi =		{10.4230/LIPIcs.GD.2024.10},
  annote =	{Keywords: String representation, outer-string, outer-1-string, chordal graphs, trees, polynomial-time algorithms, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.13
The Price of Upwardness

Authors: Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k ≥ 1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-k-planarity testing is NP-complete already for k = 1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.
Cite as

Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff. The Price of Upwardness. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.GD.2024.13,
  author =	{Angelini, Patrizio and Biedl, Therese and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Hong, Seok-Hee and Liotta, Giuseppe and Patrignani, Maurizio and Pupyrev, Sergey and Rutter, Ignaz and Wolff, Alexander},
  title =	{{The Price of Upwardness}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.13},
  URN =		{urn:nbn:de:0030-drops-212977},
  doi =		{10.4230/LIPIcs.GD.2024.13},
  annote =	{Keywords: upward drawings, beyond planarity, upward k-planarity, upward outer-1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.40
Morphing Planar Graph Drawings via Orthogonal Box Drawings

Authors: Therese Biedl, Anna Lubiw, and Jack Spalding-Jamieson

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
We give an algorithm to morph planar graph drawings that achieves small grid size at the expense of allowing a constant number of bends on each edge. The input is an n-vertex planar graph and two planar straight-line drawings of the graph on an O(n) × O(n) grid. The planarity-preserving morph is composed of O(n) linear morphs between successive pairs of drawings, each on an O(n) × O(n) grid with a constant number of bends per edge. The algorithm to compute the morph runs in O(n²) time on a word RAM model with standard arithmetic operations - in particular no square roots or cube roots are required. The first step of the algorithm is to morph each input drawing to a planar orthogonal box drawing where vertices are represented by boxes and each edge is drawn as a horizontal or vertical segment. The second step is to morph between planar orthogonal box drawings. This is done by extending known techniques for morphing planar orthogonal drawings with point vertices.
Cite as

Therese Biedl, Anna Lubiw, and Jack Spalding-Jamieson. Morphing Planar Graph Drawings via Orthogonal Box Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.GD.2024.40,
  author =	{Biedl, Therese and Lubiw, Anna and Spalding-Jamieson, Jack},
  title =	{{Morphing Planar Graph Drawings via Orthogonal Box Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.40},
  URN =		{urn:nbn:de:0030-drops-213242},
  doi =		{10.4230/LIPIcs.GD.2024.40},
  annote =	{Keywords: morphing, graph morphing, linear morph, planar graph drawing, orthogonal box drawing, orthogonal drawing, algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.24
A Parameterized Algorithm for Vertex and Edge Connectivity of Embedded Graphs

Authors: Therese Biedl, Prosenjit Bose, and Karthik Murali

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
The problem of computing vertex and edge connectivity of a graph are classical problems in algorithmic graph theory. The focus of this paper is on computing these parameters for graphs drawn on the plane. A typical example of such graphs are planar graphs which can be embedded without any crossings. It has long been known that vertex and edge connectivity of planar embedded graphs can be computed in linear time. Very recently, Biedl and Murali extended the techniques from planar graphs to 1-plane graphs without ×-crossings, i.e., crossings whose endpoints induce a matching. While the tools used were novel, they were highly tailored to 1-plane graphs, and do not provide much leeway for further extension. In this paper, we develop alternate techniques that are simpler, have wider applications to near-planar graphs, and can be used to test both vertex and edge connectivity. Our technique works for all those embedded graphs where any pair of crossing edges are connected by a path that, roughly speaking, can be covered with few cells of the drawing. Important examples of such graphs include optimal 2-planar and optimal 3-planar graphs, d-map graphs, d-framed graphs, graphs with bounded crossing number, and k-plane graphs with bounded number of ×-crossings.
Cite as

Therese Biedl, Prosenjit Bose, and Karthik Murali. A Parameterized Algorithm for Vertex and Edge Connectivity of Embedded Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ESA.2024.24,
  author =	{Biedl, Therese and Bose, Prosenjit and Murali, Karthik},
  title =	{{A Parameterized Algorithm for Vertex and Edge Connectivity of Embedded Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.24},
  URN =		{urn:nbn:de:0030-drops-210950},
  doi =		{10.4230/LIPIcs.ESA.2024.24},
  annote =	{Keywords: Vertex Connectivity, Edge Connectivity, 1-planar, k-planar, Linear-time}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.13
On the Independence Number of 1-Planar Graphs

Authors: Therese Biedl, Prosenjit Bose, and Babak Miraftab

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
An independent set in a graph is a set of vertices where no two vertices are adjacent to each other. A maximum independent set is the largest possible independent set that can be formed within a given graph G. The cardinality of this set is referred to as the independence number of G. This paper investigates the independence number of 1-planar graphs, a subclass of graphs defined by drawings in the Euclidean plane where each edge can have at most one crossing point. Borodin establishes a tight upper bound of six for the chromatic number of every 1-planar graph G, leading to a corresponding lower bound of n/6 for the independence number, where n is the number of vertices of G. In contrast, the upper bound for the independence number in 1-planar graphs is less studied. This paper addresses this gap by presenting upper bounds based on the minimum degree δ. A comprehensive table summarizes these upper bounds for various δ values, providing insights into achievable independence numbers under different conditions.
Cite as

Therese Biedl, Prosenjit Bose, and Babak Miraftab. On the Independence Number of 1-Planar Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SWAT.2024.13,
  author =	{Biedl, Therese and Bose, Prosenjit and Miraftab, Babak},
  title =	{{On the Independence Number of 1-Planar Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.13},
  URN =		{urn:nbn:de:0030-drops-200537},
  doi =		{10.4230/LIPIcs.SWAT.2024.13},
  annote =	{Keywords: 1-planar graph, independent set, minimum degree}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.23
On Computing the Vertex Connectivity of 1-Plane Graphs

Authors: Therese Biedl and Karthik Murali

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A graph is called 1-plane if it has an embedding in the plane where each edge is crossed at most once by another edge. A crossing of a 1-plane graph is called an ×-crossing if there are no other edges connecting the endpoints of the crossing (apart from the crossing pair of edges). In this paper, we show how to compute the vertex connectivity of a 1-plane graph G without ×-crossings in linear time. To do so, we show that for any two vertices u,v in a minimum separating set S, the distance between u and v in an auxiliary graph Λ(G) (obtained by planarizing G and then inserting into each face a new vertex adjacent to all vertices of the face) is small. It hence suffices to search for a minimum separating set in various subgraphs Λ_i of Λ(G) with small diameter. Since Λ(G) is planar, the subgraphs Λ_i have small treewidth. Each minimum separating set S then gives rise to a partition of Λ_i into three vertex sets with special properties; such a partition can be found via Courcelle’s theorem in linear time.
Cite as

Therese Biedl and Karthik Murali. On Computing the Vertex Connectivity of 1-Plane Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ICALP.2023.23,
  author =	{Biedl, Therese and Murali, Karthik},
  title =	{{On Computing the Vertex Connectivity of 1-Plane Graphs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.23},
  URN =		{urn:nbn:de:0030-drops-180753},
  doi =		{10.4230/LIPIcs.ICALP.2023.23},
  annote =	{Keywords: 1-Planar Graph, Connectivity, Linear Time, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.16
Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest

Authors: Sam Barr and Therese Biedl

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
1-planar graphs are graphs that can be drawn in the plane such that any edge intersects with at most one other edge. Ackerman showed that the edges of a 1-planar graph can be partitioned into a planar graph and a forest, and claims that the proof leads to a linear time algorithm. However, it is not clear how one would obtain such an algorithm from his proof. In this paper, we first reprove Ackerman’s result (in fact, we prove a slightly more general statement) and then show that the split can be found in linear time by using an edge-contraction data structure by Holm, Italiano, Karczmarz, Łącki, Rotenberg and Sankowski.
Cite as

Sam Barr and Therese Biedl. Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barr_et_al:LIPIcs.ISAAC.2021.16,
  author =	{Barr, Sam and Biedl, Therese},
  title =	{{Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.16},
  URN =		{urn:nbn:de:0030-drops-154492},
  doi =		{10.4230/LIPIcs.ISAAC.2021.16},
  annote =	{Keywords: 1-planar graphs, edge partitions, algorithms, data structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.17
Distant Representatives for Rectangles in the Plane

Authors: Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
The input to the distant representatives problem is a set of n objects in the plane and the goal is to find a representative point from each object while maximizing the distance between the closest pair of points. When the objects are axis-aligned rectangles, we give polynomial time constant-factor approximation algorithms for the L₁, L₂, and L_∞ distance measures. We also prove lower bounds on the approximation factors that can be achieved in polynomial time (unless P = NP).
Cite as

Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud. Distant Representatives for Rectangles in the Plane. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ESA.2021.17,
  author =	{Biedl, Therese and Lubiw, Anna and Naredla, Anurag Murty and Ralbovsky, Peter Dominik and Stroud, Graeme},
  title =	{{Distant Representatives for Rectangles in the Plane}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.17},
  URN =		{urn:nbn:de:0030-drops-145982},
  doi =		{10.4230/LIPIcs.ESA.2021.17},
  annote =	{Keywords: Distant representatives, blocker shapes, matching, approximation algorithm, APX-hardness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.14
Layered Fan-Planar Graph Drawings

Authors: Therese Biedl, Steven Chaplick, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg, and Chrysanthi Raftopoulou

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. In this paper, we study fan-planar drawings that use h (horizontal) layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in h, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for h = 2: It was already known how to test the existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper h-layer drawing; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.
Cite as

Therese Biedl, Steven Chaplick, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg, and Chrysanthi Raftopoulou. Layered Fan-Planar Graph Drawings. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.MFCS.2020.14,
  author =	{Biedl, Therese and Chaplick, Steven and Kaufmann, Michael and Montecchiani, Fabrizio and N\"{o}llenburg, Martin and Raftopoulou, Chrysanthi},
  title =	{{Layered Fan-Planar Graph Drawings}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.14},
  URN =		{urn:nbn:de:0030-drops-126835},
  doi =		{10.4230/LIPIcs.MFCS.2020.14},
  annote =	{Keywords: Graph Drawing, Parameterized Complexity, Beyond Planar Graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.23
Finding Tutte Paths in Linear Time

Authors: Therese Biedl and Philipp Kindermann

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
It is well-known that every planar graph has a Tutte path, i.e., a path P such that any component of G-P has at most three attachment points on P. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of G-P have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to P. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.
Cite as

Therese Biedl and Philipp Kindermann. Finding Tutte Paths in Linear Time. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ICALP.2019.23,
  author =	{Biedl, Therese and Kindermann, Philipp},
  title =	{{Finding Tutte Paths in Linear Time}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.23},
  URN =		{urn:nbn:de:0030-drops-105991},
  doi =		{10.4230/LIPIcs.ICALP.2019.23},
  annote =	{Keywords: planar graph, Tutte path, Hamiltonian path, 2-walk, linear time}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.18
Rollercoasters and Caterpillars

Authors: Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence - increasing or decreasing - has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an x-monotone polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of n distinct real numbers contains a rollercoaster of length at least ceil[n/2] for n>7, while the best known lower bound is Omega(n/log n). In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(n log n)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,...,n} can be computed in O(n log log n) time. The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of maximum degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every n-vertex top-view caterpillar on every set of 25/3(n+4) points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is O(n log n). We also show that such a drawing can be obtained in linear time, when the points are given in sorted order.
Cite as

Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit. Rollercoasters and Caterpillars. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ICALP.2018.18,
  author =	{Biedl, Therese and Biniaz, Ahmad and Cummings, Robert and Lubiw, Anna and Manea, Florin and Nowotka, Dirk and Shallit, Jeffrey},
  title =	{{Rollercoasters and Caterpillars}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.18},
  URN =		{urn:nbn:de:0030-drops-90224},
  doi =		{10.4230/LIPIcs.ICALP.2018.18},
  annote =	{Keywords: sequences, alternating runs, patterns in permutations, caterpillars}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.10
On the Size of Outer-String Representations

Authors: Therese Biedl, Ahmad Biniaz, and Martin Derka

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
Outer-string graphs, i.e., graphs that can be represented as intersection of curves in 2D, all of which end in the outer-face, have recently received much interest, especially since it was shown that the independent set problem can be solved efficiently in such graphs. However, the run-time for the independent set problem depends on N, the number of segments in an outer-string representation, rather than the number n of vertices of the graph. In this paper, we argue that for some outer-string graphs, N must be exponential in n. We also study some special string graphs, viz. monotone string graphs, and argue that for them N can be assumed to be polynomial in n. Finally we give an algorithm for independent set in so-called strip-grounded monotone outer-string graphs that is polynomial in n.
Cite as

Therese Biedl, Ahmad Biniaz, and Martin Derka. On the Size of Outer-String Representations. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SWAT.2018.10,
  author =	{Biedl, Therese and Biniaz, Ahmad and Derka, Martin},
  title =	{{On the Size of Outer-String Representations}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.10},
  URN =		{urn:nbn:de:0030-drops-88360},
  doi =		{10.4230/LIPIcs.SWAT.2018.10},
  annote =	{Keywords: string graph, outer-string graph, size of representation, independent set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.13
Crossing Number for Graphs with Bounded~Pathwidth

Authors: Therese Biedl, Markus Chimani, Martin Derka, and Petra Mutzel

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we for the first time show that crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an O(n)xO(n)-grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3, and a 4w^3-approximation for maximal graphs of pathwidth w. This is a constant approximation for bounded pathwidth graphs.
Cite as

Therese Biedl, Markus Chimani, Martin Derka, and Petra Mutzel. Crossing Number for Graphs with Bounded~Pathwidth. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ISAAC.2017.13,
  author =	{Biedl, Therese and Chimani, Markus and Derka, Martin and Mutzel, Petra},
  title =	{{Crossing Number for Graphs with Bounded\textasciitildePathwidth}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.13},
  URN =		{urn:nbn:de:0030-drops-82570},
  doi =		{10.4230/LIPIcs.ISAAC.2017.13},
  annote =	{Keywords: Crossing Number, Graphs with Bounded Pathwidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.17
On r-Guarding Thin Orthogonal Polygons

Authors: Therese Biedl and Saeed Mehrabi

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Guarding a polygon with few guards is an old and well-studied problem in computational geometry. Here we consider the following variant: We assume that the polygon is orthogonal and thin in some sense, and we consider a point p to guard a point q if and only if the minimum axis-aligned rectangle spanned by p and q is inside the polygon. A simple proof shows that this problem is NP-hard on orthogonal polygons with holes, even if the polygon is thin. If there are no holes, then a thin polygon becomes a tree polygon in the sense that the so-called dual graph of the polygon is a tree. It was known that finding the minimum set of r-guards is polynomial for tree polygons (and in fact for all orthogonal polygons), but the run-time was ~O(n^17). We show here that with a different approach one can find the minimum set of r-guards can be found in tree polygons in linear time, answering a question posed by Biedl et al. (SoCG 2011). Furthermore, the approach is much more general, allowing to specify subsets of points to guard and guards to use, and it generalizes to polygons with h holes or thickness K, becoming fixed-parameter tractable in h + K.
Cite as

Therese Biedl and Saeed Mehrabi. On r-Guarding Thin Orthogonal Polygons. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ISAAC.2016.17,
  author =	{Biedl, Therese and Mehrabi, Saeed},
  title =	{{On r-Guarding Thin Orthogonal Polygons}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.17},
  URN =		{urn:nbn:de:0030-drops-67913},
  doi =		{10.4230/LIPIcs.ISAAC.2016.17},
  annote =	{Keywords: Art Gallery Problem, Orthogonal Polygons, r-Guarding, Treewidth, Fixed-parameter Tractable}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.19
On Visibility Representations of Non-Planar Graphs

Authors: Therese Biedl, Giuseppe Liotta, and Fabrizio Montecchiani

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.
Cite as

Therese Biedl, Giuseppe Liotta, and Fabrizio Montecchiani. On Visibility Representations of Non-Planar Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SoCG.2016.19,
  author =	{Biedl, Therese and Liotta, Giuseppe and Montecchiani, Fabrizio},
  title =	{{On Visibility Representations of Non-Planar Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.19},
  URN =		{urn:nbn:de:0030-drops-59116},
  doi =		{10.4230/LIPIcs.SoCG.2016.19},
  annote =	{Keywords: Visibility Representations, 1-Planarity, Recognition Algorithm, Forbidden Configuration}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.141
1-String B_2-VPG Representation of Planar Graphs

Authors: Therese Biedl and Martin Derka

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
In this paper, we prove that every planar graph has a 1-string B_2-VPG representation - a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices u, v intersect precisely once whenever there is an edge between u and v.
Cite as

Therese Biedl and Martin Derka. 1-String B_2-VPG Representation of Planar Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 141-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SOCG.2015.141,
  author =	{Biedl, Therese and Derka, Martin},
  title =	{{1-String B\underline2-VPG Representation of Planar Graphs}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{141--155},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.141},
  URN =		{urn:nbn:de:0030-drops-51323},
  doi =		{10.4230/LIPIcs.SOCG.2015.141},
  annote =	{Keywords: Graph drawing, string graphs, VPG graphs, planar graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact