Search Results

Documents authored by Eppstein, David

Document
DOI: 10.4230/LIPIcs.GD.2024.36
Noncrossing Longest Paths and Cycles

Authors: Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr

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

Abstract
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.
Cite as

Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr. Noncrossing Longest Paths and Cycles. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aloupis_et_al:LIPIcs.GD.2024.36,
  author =	{Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Eppstein, David and Maheshwari, Anil and Odak, Saeed and Smid, Michiel and T\'{o}th, Csaba D. and Valtr, Pavel},
  title =	{{Noncrossing Longest Paths and Cycles}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{36:1--36:17},
  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.36},
  URN =		{urn:nbn:de:0030-drops-213203},
  doi =		{10.4230/LIPIcs.GD.2024.36},
  annote =	{Keywords: Longest Paths, Longest Cycles, Noncrossing Paths, Noncrossing Cycles}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.39
Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature

Authors: David Eppstein, Michael T. Goodrich, and Abraham M. Illickan

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

Abstract
We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC drawing using a single cubic Bézier curve per edge, and this drawing can be computed in O(n) time given a combinatorial 1-planar drawing. We also show that any n-vertex planar graph G can be drawn in O(n) time with a single cubic Bézier curve per edge, in an O(n)× O(n) bounding box, such that the edges have Θ(1/degree(v)) angular resolution, for each v ∈ G, and O(√n) curvature.
Cite as

David Eppstein, Michael T. Goodrich, and Abraham M. Illickan. Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.GD.2024.39,
  author =	{Eppstein, David and Goodrich, Michael T. and Illickan, Abraham M.},
  title =	{{Drawing Planar Graphs and 1-Planar Graphs Using Cubic B\'{e}zier Curves with Bounded Curvature}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{39:1--39:17},
  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.39},
  URN =		{urn:nbn:de:0030-drops-213237},
  doi =		{10.4230/LIPIcs.GD.2024.39},
  annote =	{Keywords: graph drawing, planar graphs, B\'{e}zier curves, and RAC drawings}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.30
Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs

Authors: David Eppstein and Daniel Frishberg

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We give a new rapid mixing result for a natural random walk on the independent sets of a graph G. We show that when G has bounded treewidth, this random walk - known as the Glauber dynamics for the hardcore model - mixes rapidly for all fixed values of the standard parameter λ > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets, b-edge covers, b-matchings, maximal independent sets, and maximal b-matchings. (For b-matchings, maximal independent sets, and maximal b-matchings we also require bounded degree.) Our results imply simpler alternatives to known algorithms for the sampling and approximate counting problems in these graphs. We prove our results by applying a divide-and-conquer framework we developed in a previous paper, as an alternative to the projection-restriction technique introduced by Jerrum, Son, Tetali, and Vigoda. We extend this prior framework to handle chains for which the application of that framework is not straightforward, strengthening existing results by Dyer, Goldberg, and Jerrum and by Heinrich for the Glauber dynamics on q-colorings of graphs of bounded treewidth and bounded degree.
Cite as

David Eppstein and Daniel Frishberg. Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ISAAC.2023.30,
  author =	{Eppstein, David and Frishberg, Daniel},
  title =	{{Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.30},
  URN =		{urn:nbn:de:0030-drops-193324},
  doi =		{10.4230/LIPIcs.ISAAC.2023.30},
  annote =	{Keywords: Glauber dynamics, mixing time, projection-restriction, multicommodity flow}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.56
Improved Mixing for the Convex Polygon Triangulation Flip Walk

Authors: David Eppstein and Daniel Frishberg

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

Abstract
We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n³ log³ n), the first progress since McShine and Tetali’s O(n⁵ log n) bound in 1997. In the process we give lower and upper bounds of respectively Ω(1/(√n log n)) and O(1/√n) - asymptotically tight up to an O(log n) factor - for the expansion of the associahedron graph K_n. The upper bound recovers Molloy, Reed, and Steiger’s Ω(n^(3/2)) bound on the mixing time of the walk. To obtain these results, we introduce a framework consisting of a set of sufficient conditions under which a given Markov chain mixes rapidly. This framework is a purely combinatorial analogue that in some circumstances gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda. In particular, in addition to the result for triangulations, we show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k ≥ 4.
Cite as

David Eppstein and Daniel Frishberg. Improved Mixing for the Convex Polygon Triangulation Flip Walk. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ICALP.2023.56,
  author =	{Eppstein, David and Frishberg, Daniel},
  title =	{{Improved Mixing for the Convex Polygon Triangulation Flip Walk}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{56:1--56:17},
  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.56},
  URN =		{urn:nbn:de:0030-drops-181081},
  doi =		{10.4230/LIPIcs.ICALP.2023.56},
  annote =	{Keywords: associahedron, mixing time, mcmc, Markov chains, triangulations, quadrangulations, k-angulations, multicommodity flow, projection-restriction}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.29
Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time

Authors: David Eppstein

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers.
Cite as

David Eppstein. Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.SoCG.2023.29,
  author =	{Eppstein, David},
  title =	{{Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.29},
  URN =		{urn:nbn:de:0030-drops-178790},
  doi =		{10.4230/LIPIcs.SoCG.2023.29},
  annote =	{Keywords: polygonalization, non-crossing structures, output-sensitive algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.21
Distributed Construction of Lightweight Spanners for Unit Ball Graphs

Authors: David Eppstein and Hadi Khodabandeh

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Resolving an open question from 2006 [Damian et al., 2006], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple 𝒪(log^*n)-round distributed algorithm in the LOCAL model of computation, that given a unit ball graph G with n vertices and a positive constant ε < 1 finds a (1+ε)-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the best prior lightness bound, the algorithm of Damian, Pandit, and Pemmaraju [Damian et al., 2006], which runs in 𝒪(log^*n) rounds in the LOCAL model, but has a 𝒪(log Δ) bound on its lightness, where Δ is the ratio of the length of the longest edge to the length of the shortest edge in the unit ball graph. Next, we adjust our algorithm to work in the CONGEST model, without changing its round complexity, hence proposing the first spanner construction for unit ball graphs in the CONGEST model of computation. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersections per node. Lastly, we provide experimental results that confirm our theoretical bounds, and show an efficient performance from our distributed algorithm compared to the best known centralized construction.
Cite as

David Eppstein and Hadi Khodabandeh. Distributed Construction of Lightweight Spanners for Unit Ball Graphs. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.DISC.2022.21,
  author =	{Eppstein, David and Khodabandeh, Hadi},
  title =	{{Distributed Construction of Lightweight Spanners for Unit Ball Graphs}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{21:1--21:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.21},
  URN =		{urn:nbn:de:0030-drops-172129},
  doi =		{10.4230/LIPIcs.DISC.2022.21},
  annote =	{Keywords: spanners, doubling metrics, distributed, topology control}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.33
On the Edge Crossings of the Greedy Spanner

Authors: David Eppstein and Hadi Khodabandeh

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
The greedy t-spanner of a set of points in the plane is an undirected graph constructed by considering pairs of points in order by distance, and connecting a pair by an edge when there does not already exist a path connecting that pair with length at most t times the Euclidean distance. We prove that, for any t > 1, these graphs have at most a linear number of crossings, and more strongly that the intersection graph of edges in a greedy t-spanner has bounded degeneracy. As a consequence, we prove a separator theorem for greedy spanners: any k-vertex subgraph of a greedy spanner can be partitioned into sub-subgraphs of size a constant fraction smaller, by the removal of O(√k) vertices. A recursive separator hierarchy for these graphs can be constructed from their planarizations in linear time, or in near-linear time if the planarization is unknown.
Cite as

David Eppstein and Hadi Khodabandeh. On the Edge Crossings of the Greedy Spanner. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.SoCG.2021.33,
  author =	{Eppstein, David and Khodabandeh, Hadi},
  title =	{{On the Edge Crossings of the Greedy Spanner}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.33},
  URN =		{urn:nbn:de:0030-drops-138328},
  doi =		{10.4230/LIPIcs.SoCG.2021.33},
  annote =	{Keywords: Geometric Spanners, Greedy Spanners, Separators, Crossing Graph, Sparsity}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.13
On the Treewidth of Hanoi Graphs

Authors: David Eppstein, Daniel Frishberg, and William Maxwell

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.
Cite as

David Eppstein, Daniel Frishberg, and William Maxwell. On the Treewidth of Hanoi Graphs. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.FUN.2021.13,
  author =	{Eppstein, David and Frishberg, Daniel and Maxwell, William},
  title =	{{On the Treewidth of Hanoi Graphs}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.13},
  URN =		{urn:nbn:de:0030-drops-127741},
  doi =		{10.4230/LIPIcs.FUN.2021.13},
  annote =	{Keywords: Hanoi graph, Treewidth, Graph separators, Kneser graph, Vertex expansion, Haven, Tensor product}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.15
Low-Stretch Spanning Trees of Graphs with Bounded Width

Authors: Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, and Amir Nayyeri

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph G with a linear arrangement of bandwidth b can be embedded into a distribution T of spanning trees such that the expected stretch of each edge of G is O(b²). Our proof implies a linear time algorithm for sampling from T. Therefore, we have a linear time algorithm that finds a spanning tree of G with average stretch O(b²) with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of G with average stretch O(b³). For graphs of cutwidth c, we construct a spanning tree with stretch O(c²) in linear time. Finally, when G has treewidth k we provide a dynamic programming algorithm computing a minimum stretch spanning tree of G that runs in polynomial time with respect to the number of vertices of G.
Cite as

Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, and Amir Nayyeri. Low-Stretch Spanning Trees of Graphs with Bounded Width. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SWAT.2020.15,
  author =	{Borradaile, Glencora and Chambers, Erin Wolf and Eppstein, David and Maxwell, William and Nayyeri, Amir},
  title =	{{Low-Stretch Spanning Trees of Graphs with Bounded Width}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.15},
  URN =		{urn:nbn:de:0030-drops-122622},
  doi =		{10.4230/LIPIcs.SWAT.2020.15},
  annote =	{Keywords: Treewidth, low-stretch spanning tree, fundamental cycle basis}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.24
Simplifying Activity-On-Edge Graphs

Authors: David Eppstein, Daniel Frishberg, and Elham Havvaei

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges represent either tasks of the project or timing constraints between milestones. In this framework, a timeline of the project can be constructed as a leveled drawing of the graph, where the levels of the vertices represent the time at which each milestone is scheduled to happen. We focus on the following problem: given an activity-on-edge graph representing a project, find an equivalent activity-on-edge graph—one with the same critical paths—that has the minimum possible number of milestone vertices among all equivalent activity-on-edge graphs. We provide an O(mn²)-time algorithm for solving this graph minimization problem.
Cite as

David Eppstein, Daniel Frishberg, and Elham Havvaei. Simplifying Activity-On-Edge Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.SWAT.2020.24,
  author =	{Eppstein, David and Frishberg, Daniel and Havvaei, Elham},
  title =	{{Simplifying Activity-On-Edge Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.24},
  URN =		{urn:nbn:de:0030-drops-122718},
  doi =		{10.4230/LIPIcs.SWAT.2020.24},
  annote =	{Keywords: directed acyclic graph, activity-on-edge graph, critical path, project planning, milestone minimization, graph visualization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.9
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width

Authors: Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA'95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT algorithm for embedded clustered graphs, when parameterized by the carving-width of the dual graph of the input. This is the first FPT algorithm for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. To further strengthen the relevance of this result, we show that the C-Planarity Testing problem retains its computational complexity when parameterized by several other graph-width parameters, which may potentially lead to faster algorithms.
Cite as

Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.IPEC.2019.9,
  author =	{Da Lozzo, Giordano and Eppstein, David and Goodrich, Michael T. and Gupta, Siddharth},
  title =	{{C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.9},
  URN =		{urn:nbn:de:0030-drops-114705},
  doi =		{10.4230/LIPIcs.IPEC.2019.9},
  annote =	{Keywords: Clustered planarity, carving-width, non-crossing partitions, FPT}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.51
New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

Authors: Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We use it to construct the greedy multi-fragment tour for Euclidean TSP in O(n log n) time in any fixed dimension and for Steiner TSP in planar graphs in O(n sqrt(n)log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n^(4/3+epsilon)) time for any epsilon>0.
Cite as

Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk. New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mamano_et_al:LIPIcs.ISAAC.2019.51,
  author =	{Mamano, Nil and Efrat, Alon and Eppstein, David and Frishberg, Daniel and Goodrich, Michael T. and Kobourov, Stephen and Matias, Pedro and Polishchuk, Valentin},
  title =	{{New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.51},
  URN =		{urn:nbn:de:0030-drops-115477},
  doi =		{10.4230/LIPIcs.ISAAC.2019.51},
  annote =	{Keywords: Nearest-neighbors, Nearest-neighbor chain, motorcycle graph, straight skeleton, multi-fragment algorithm, Euclidean TSP, Steiner TSP}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.54
Tracking Paths in Planar Graphs

Authors: David Eppstein, Michael T. Goodrich, James A. Liu, and Pedro Matias

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et al. [Banik et al., 2017]. Given an undirected graph with a source s and a destination t, find the smallest subset of vertices whose intersection with any s-t path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelle’s theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.
Cite as

David Eppstein, Michael T. Goodrich, James A. Liu, and Pedro Matias. Tracking Paths in Planar Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ISAAC.2019.54,
  author =	{Eppstein, David and Goodrich, Michael T. and Liu, James A. and Matias, Pedro},
  title =	{{Tracking Paths in Planar Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.54},
  URN =		{urn:nbn:de:0030-drops-115500},
  doi =		{10.4230/LIPIcs.ISAAC.2019.54},
  annote =	{Keywords: Approximation Algorithm, Courcelle’s Theorem, Clique-Width, Planar, 3-SAT, Graph Algorithms, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.32
Cubic Planar Graphs That Cannot Be Drawn On Few Lines

Authors: David Eppstein

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
For every integer l, we construct a cubic 3-vertex-connected planar bipartite graph G with O(l^3) vertices such that there is no planar straight-line drawing of G whose vertices all lie on l lines. This strengthens previous results on graphs that cannot be drawn on few lines, which constructed significantly larger maximal planar graphs. We also find apex-trees and cubic bipartite series-parallel graphs that cannot be drawn on a bounded number of lines.
Cite as

David Eppstein. Cubic Planar Graphs That Cannot Be Drawn On Few Lines. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.SoCG.2019.32,
  author =	{Eppstein, David},
  title =	{{Cubic Planar Graphs That Cannot Be Drawn On Few Lines}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.32},
  URN =		{urn:nbn:de:0030-drops-104363},
  doi =		{10.4230/LIPIcs.SoCG.2019.32},
  annote =	{Keywords: graph drawing, universal point sets, collinearity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.33
Counting Polygon Triangulations is Hard

Authors: David Eppstein

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We prove that it is #P-complete to count the triangulations of a (non-simple) polygon.
Cite as

David Eppstein. Counting Polygon Triangulations is Hard. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.SoCG.2019.33,
  author =	{Eppstein, David},
  title =	{{Counting Polygon Triangulations is Hard}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.33},
  URN =		{urn:nbn:de:0030-drops-104371},
  doi =		{10.4230/LIPIcs.SoCG.2019.33},
  annote =	{Keywords: counting complexity, #P-completeness, triangulation, polygons}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.11
The Parameterized Complexity of Finding Point Sets with Hereditary Properties

Authors: David Eppstein and Daniel Lokshtanov

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
We consider problems where the input is a set of points in the plane and an integer k, and the task is to find a subset S of the input points of size k such that S satisfies some property. We focus on properties that depend only on the order type of the points and are monotone under point removals. We exhibit a property defined by three forbidden patterns for which finding a k-point subset with the property is W[1]-complete and (assuming the exponential time hypothesis) cannot be solved in time n^{o(k/log k)}. However, we show that problems of this type are fixed-parameter tractable for all properties that include all collinear point sets, properties that exclude at least one convex polygon, and properties defined by a single forbidden pattern.
Cite as

David Eppstein and Daniel Lokshtanov. The Parameterized Complexity of Finding Point Sets with Hereditary Properties. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.IPEC.2018.11,
  author =	{Eppstein, David and Lokshtanov, Daniel},
  title =	{{The Parameterized Complexity of Finding Point Sets with Hereditary Properties}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.11},
  URN =		{urn:nbn:de:0030-drops-102121},
  doi =		{10.4230/LIPIcs.IPEC.2018.11},
  annote =	{Keywords: parameterized complexity, fixed-parameter tractability, point set pattern matching, largest pattern-avoiding subset, order type}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.16
Parameterized Leaf Power Recognition via Embedding into Graph Products

Authors: David Eppstein and Elham Havvaei

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
The k-leaf power graph G of a tree T is a graph whose vertices are the leaves of T and whose edges connect pairs of leaves at unweighted distance at most k in T. Recognition of the k-leaf power graphs for k >= 6 is still an open problem. In this paper, we provide an algorithm for this problem for sparse leaf power graphs. Our result shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by k and by the degeneracy of the given graph. To prove this, we describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of k and the degeneracy of G. As a result, we can use methods based on monadic second-order logic (MSO_2) to recognize the existence of a leaf power as a subgraph of the product graph.
Cite as

David Eppstein and Elham Havvaei. Parameterized Leaf Power Recognition via Embedding into Graph Products. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.IPEC.2018.16,
  author =	{Eppstein, David and Havvaei, Elham},
  title =	{{Parameterized Leaf Power Recognition via Embedding into Graph Products}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.16},
  URN =		{urn:nbn:de:0030-drops-102179},
  doi =		{10.4230/LIPIcs.IPEC.2018.16},
  annote =	{Keywords: leaf power, phylogenetic tree, monadic second-order logic, Courcelle's theorem, strong product of graphs, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.81
Optimally Sorting Evolving Data

Authors: Juan Jose Besa, William E. Devanny, David Eppstein, Michael T. Goodrich, and Timothy Johnson

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

Abstract
We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.
Cite as

Juan Jose Besa, William E. Devanny, David Eppstein, Michael T. Goodrich, and Timothy Johnson. Optimally Sorting Evolving Data. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.ICALP.2018.81,
  author =	{Besa, Juan Jose and Devanny, William E. and Eppstein, David and Goodrich, Michael T. and Johnson, Timothy},
  title =	{{Optimally Sorting Evolving Data}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{81:1--81:13},
  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.81},
  URN =		{urn:nbn:de:0030-drops-90858},
  doi =		{10.4230/LIPIcs.ICALP.2018.81},
  annote =	{Keywords: Sorting, Evolving data, Insertion sort}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.89
Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

Authors: Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano

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

Abstract
We study algorithms and combinatorial complexity bounds for stable-matching Voronoi diagrams, where a set, S, of n point sites in the plane determines a stable matching between the points in R^2 and the sites in S such that (i) the points prefer sites closer to them and sites prefer points closer to them, and (ii) each site has a quota indicating the area of the set of points that can be matched to it. Thus, a stable-matching Voronoi diagram is a solution to the classic post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. We show that a stable-matching Voronoi diagram of n sites has O(n^{2+epsilon}) faces and edges, for any epsilon>0, and show that this bound is almost tight by giving a family of diagrams with Theta(n^2) faces and edges. We also provide a discrete algorithm for constructing it in O(n^3+n^2f(n)) time, where f(n) is the runtime of a geometric primitive that can be performed in the real-RAM model or can be approximated numerically. This is necessary, as the diagram cannot be computed exactly in an algebraic model of computation.
Cite as

Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano. Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.ICALP.2018.89,
  author =	{Barequet, Gill and Eppstein, David and Goodrich, Michael T. and Mamano, Nil},
  title =	{{Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{89:1--89:14},
  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.89},
  URN =		{urn:nbn:de:0030-drops-90937},
  doi =		{10.4230/LIPIcs.ICALP.2018.89},
  annote =	{Keywords: Voronoi diagram, stable matching, combinatorial complexity, lower bounds}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SWAT.2018
LIPIcs, Volume 101, SWAT'18, Complete Volume

Authors: David Eppstein

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

Abstract
LIPIcs, Volume 101, SWAT'18, Complete Volume
Cite as

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{eppstein:LIPIcs.SWAT.2018,
  title =	{{LIPIcs, Volume 101, SWAT'18, Complete Volume}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  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},
  URN =		{urn:nbn:de:0030-drops-89329},
  doi =		{10.4230/LIPIcs.SWAT.2018},
  annote =	{Keywords: Theory of computation, Design and analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.20
Faster Evaluation of Subtraction Games

Authors: David Eppstein

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Subtraction games are played with one or more heaps of tokens, with players taking turns removing from a single heap a number of tokens belonging to a specified subtraction set; the last player to move wins. We describe how to compute the set of winning heap sizes in single-heap subtraction games (for an input consisting of the subtraction set and maximum heap size n), in time O~(n), where the O~ elides logarithmic factors. For multi-heap games, the optimal game play is determined by the nim-value of each heap; we describe how to compute the nim-values of all heaps of size up to n in time O~(mn), where m is the maximum nim-value occurring among these heap sizes. These time bounds improve naive dynamic programming algorithms with time O(n|S|), because m <=|S| for all such games. We apply these results to the game of subtract-a-square, whose set of winning positions is a maximal square-difference-free set of a type studied in number theory in connection with the Furstenberg-Sárközy theorem. We provide experimental evidence that, for this game, the set of winning positions has a density comparable to that of the densest known square-difference-free sets, and has a modular structure related to the known constructions for these dense sets. Additionally, this game's nim-values are (experimentally) significantly smaller than the size of its subtraction set, implying that our algorithm achieves a polynomial speedup over dynamic programming.
Cite as

David Eppstein. Faster Evaluation of Subtraction Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.FUN.2018.20,
  author =	{Eppstein, David},
  title =	{{Faster Evaluation of Subtraction Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{20:1--20:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.20},
  URN =		{urn:nbn:de:0030-drops-88119},
  doi =		{10.4230/LIPIcs.FUN.2018.20},
  annote =	{Keywords: subtraction games, Sprague-Grundy theory, nim-values}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.21
Making Change in 2048

Authors: David Eppstein

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
The 2048 game involves tiles labeled with powers of two that can be merged to form bigger powers of two; variants of the same puzzle involve similar merges of other tile values. We analyze the maximum score achievable in these games by proving a min-max theorem equating this maximum score (in an abstract generalized variation of 2048 that allows all the moves of the original game) with the minimum value that causes a greedy change-making algorithm to use a given number of coins. A widely-followed strategy in 2048 maintains tiles that represent the move number in binary notation, and a similar strategy in the Fibonacci number variant of the game (987) maintains the Zeckendorf representation of the move number as a sum of the fewest possible Fibonacci numbers; our analysis shows that the ability to follow these strategies is intimately connected with the fact that greedy change-making is optimal for binary and Fibonacci coinage. For variants of 2048 using tile values for which greedy change-making is suboptimal, it is the greedy strategy, not the optimal representation as sums of tile values, that controls the length of the game. In particular, the game will always terminate whenever the sequence of allowable tile values has arbitrarily large gaps between consecutive values.
Cite as

David Eppstein. Making Change in 2048. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.FUN.2018.21,
  author =	{Eppstein, David},
  title =	{{Making Change in 2048}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.21},
  URN =		{urn:nbn:de:0030-drops-88124},
  doi =		{10.4230/LIPIcs.FUN.2018.21},
  annote =	{Keywords: 2048, change-making problem, greedy algorithm, integer sequences, halting problem}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SWAT.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: David Eppstein

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 0:i-0:ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.SWAT.2018.0,
  author =	{Eppstein, David},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{0:i--0:ix},
  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.0},
  URN =		{urn:nbn:de:0030-drops-88264},
  doi =		{10.4230/LIPIcs.SWAT.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.16
K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

Authors: David Eppstein and Denis Kurz

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We show that, for any graph optimization problem in which the feasible solutions can be expressed by a formula in monadic second-order logic describing sets of vertices or edges and in which the goal is to minimize the sum of the weights in the selected sets, we can find the k best solution values for n-vertex graphs of bounded treewidth in time O(n + k log n). In particular, this applies to finding the k shortest simple paths between given vertices in directed graphs of bounded treewidth, giving an exponential speedup in the per-path cost over previous algorithms.
Cite as

David Eppstein and Denis Kurz. K-Best Solutions of MSO Problems on Tree-Decomposable Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.IPEC.2017.16,
  author =	{Eppstein, David and Kurz, Denis},
  title =	{{K-Best Solutions of MSO Problems on Tree-Decomposable Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.16},
  URN =		{urn:nbn:de:0030-drops-85494},
  doi =		{10.4230/LIPIcs.IPEC.2017.16},
  annote =	{Keywords: graph algorithm, k-best, monadic second-order logic, treewidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.24
Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs

Authors: Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson

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

Abstract
A square-contact representation of a planar graph G = (V,E) maps vertices in V to interior-disjoint axis-aligned squares in the plane and edges in E to adjacencies between the sides of the corresponding squares. In this paper, we study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points. We characterize the partial 2-trees and the triconnected cycle-trees allowing for such representations. For partial 2-trees our characterization uses a simple forbidden subgraph whose structure forces a separating triangle in any embedding. For the triconnected cycle-trees, a subclass of the triconnected simply-nested graphs, we use a new structural decomposition for the graphs in this family, which may be of independent interest. Finally, we study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index.
Cite as

Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson. Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2017.24,
  author =	{Da Lozzo, Giordano and Devanny, William E. and Eppstein, David and Johnson, Timothy},
  title =	{{Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{24:1--24:14},
  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.24},
  URN =		{urn:nbn:de:0030-drops-82675},
  doi =		{10.4230/LIPIcs.ISAAC.2017.24},
  annote =	{Keywords: Square-Contact Representations, Partial 2-Trees, Simply-Nested Graphs}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.5
Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection

Authors: Juan José Besa Vial, William E. Devanny, David Eppstein, and Michael T. Goodrich

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should wait so that others can go through, so as to minimize the maximum delay for any vehicle. We provide polynomial-time algorithms for constructing such schedules for a k-way merge intersection, for constant k, and for a crossing intersection involving two-way traffic. We also show that the more general problem of scheduling autonomous platoons through an intersection that includes both a k-way merge, for non-constant k, and a crossing of two-way traffic is NP-complete.
Cite as

Juan José Besa Vial, William E. Devanny, David Eppstein, and Michael T. Goodrich. Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{besavial_et_al:OASIcs.ATMOS.2016.5,
  author =	{Besa Vial, Juan Jos\'{e} and Devanny, William E. and Eppstein, David and Goodrich, Michael T.},
  title =	{{Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{5:1--5:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.5},
  URN =		{urn:nbn:de:0030-drops-65296},
  doi =		{10.4230/OASIcs.ATMOS.2016.5},
  annote =	{Keywords: autonomous vehicles, platoons, scheduling}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.8
Cuckoo Filter: Simplification and Analysis

Authors: David Eppstein

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
The cuckoo filter data structure of Fan, Andersen, Kaminsky, and Mitzenmacher (CoNEXT 2014) performs the same approximate set operations as a Bloom filter in less memory, with better locality of reference, and adds the ability to delete elements as well as to insert them. However, until now it has lacked theoretical guarantees on its performance. We describe a simplified version of the cuckoo filter using fewer hash function calls per query. With this simplification, we provide the first theoretical performance guarantees on cuckoo filters, showing that they succeed with high probability whenever their fingerprint length is large enough.
Cite as

David Eppstein. Cuckoo Filter: Simplification and Analysis. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.SWAT.2016.8,
  author =	{Eppstein, David},
  title =	{{Cuckoo Filter: Simplification and Analysis}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{8:1--8:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.8},
  URN =		{urn:nbn:de:0030-drops-60264},
  doi =		{10.4230/LIPIcs.SWAT.2016.8},
  annote =	{Keywords: approximate set, Bloom filter, cuckoo filter, cuckoo hashing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.22
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Authors: Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen

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

Abstract
For an undirected n-vertex graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a minimum st-cut in G? We solve this problem in preprocessing time O(n log^3 n) for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space O(n) that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is 2^{O(g^2)}.
Cite as

Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.22,
  author =	{Borradaile, Glencora and Eppstein, David and Nayyeri, Amir and Wulff-Nilsen, Christian},
  title =	{{All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{22:1--22: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.22},
  URN =		{urn:nbn:de:0030-drops-59149},
  doi =		{10.4230/LIPIcs.SoCG.2016.22},
  annote =	{Keywords: minimum cuts, surface-embedded graphs, Gomory-Hu tree}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.240
Finding All Maximal Subsequences with Hereditary Properties

Authors: Drago Bokal, Sergio Cabello, and David Eppstein

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

Abstract
Consider a sequence s_1,...,s_n of points in the plane. We want to find all maximal subsequences with a given hereditary property P: find for all indices i the largest index j^*(i) such that s_i,...,s_{j^*(i)} has property P. We provide a general methodology that leads to the following specific results: - In O(n log^2 n) time we can find all maximal subsequences with diameter at most 1. - In O(n log n loglog n) time we can find all maximal subsequences whose convex hull has area at most 1. - In O(n) time we can find all maximal subsequences that define monotone paths in some (subpath-dependent) direction. The same methodology works for graph planarity, as follows. Consider a sequence of edges e_1,...,e_n over a vertex set V. In O(n log n) time we can find, for all indices i, the largest index j^*(i) such that (V,{e_i,..., e_{j^*(i)}}) is planar.
Cite as

Drago Bokal, Sergio Cabello, and David Eppstein. Finding All Maximal Subsequences with Hereditary Properties. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 240-254, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bokal_et_al:LIPIcs.SOCG.2015.240,
  author =	{Bokal, Drago and Cabello, Sergio and Eppstein, David},
  title =	{{Finding All Maximal Subsequences with Hereditary Properties}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{240--254},
  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.240},
  URN =		{urn:nbn:de:0030-drops-51132},
  doi =		{10.4230/LIPIcs.SOCG.2015.240},
  annote =	{Keywords: convex hull, diameter, monotone path, sequence of points, trajectory}
}
Document
DOI: 10.4230/DagSemProc.10441.2
Listing all maximal cliques in sparse graphs in near-optimal time

Authors: David Eppstein, Maarten Löffler, and Darren Strash

Published in: Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)

Abstract
The degeneracy of an $n$-vertex graph $G$ is the smallest number $d$ such that every subgraph of $G$ contains a vertex of degree at most $d$. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron--Kerbosch algorithm and show that it runs in time $O(dn3^{d/3})$. We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an $n$-vertex graph with degeneracy $d$ (when $d$ is a multiple of 3 and $nge d+3$) is $(n-d)3^{d/3}$. Therefore, our algorithm matches the $Theta(d(n-d)3^{d/3})$ worst-case output size of the problem whenever $n-d=Omega(n)$.
Cite as

David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:DagSemProc.10441.2,
  author =	{Eppstein, David and L\"{o}ffler, Maarten and Strash, Darren},
  title =	{{Listing all maximal cliques in sparse graphs in near-optimal time}},
  booktitle =	{Exact Complexity of NP-hard Problems},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10441},
  editor =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.2},
  URN =		{urn:nbn:de:0030-drops-29356},
  doi =		{10.4230/DagSemProc.10441.2},
  annote =	{Keywords: Clique, backtracking, degeneracy, worst-case optimality}
}
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