Search Results

Documents authored by Goodrich, Michael

Found 2 Possible Name Variants:

Goodrich, Michael T.

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
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.52
Polygonally Anchored Graph Drawing (Poster Abstract)

Authors: Alvin Chiu, Ahmed Eldawy, and Michael T. Goodrich

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

Abstract
We investigate force-directed graph drawing techniques under the constraint that some nodes must be anchored to stay within a given polygonal region associated with it (i.e. some positional information is known). The low energy layouts produced by such algorithms may reveal geographic information about nodes with no such knowledge a priori. Some applications of graph drawing with partial positional information include location-based social networks and rail networks, where the geographical locations need not be precise.
Cite as

Alvin Chiu, Ahmed Eldawy, and Michael T. Goodrich. Polygonally Anchored Graph Drawing (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.GD.2024.52,
  author =	{Chiu, Alvin and Eldawy, Ahmed and Goodrich, Michael T.},
  title =	{{Polygonally Anchored Graph Drawing}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{52:1--52:3},
  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.52},
  URN =		{urn:nbn:de:0030-drops-213369},
  doi =		{10.4230/LIPIcs.GD.2024.52},
  annote =	{Keywords: polygonal anchors, force-directed}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.8
Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors

Authors: Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.
Cite as

Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8,
  author =	{Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim},
  title =	{{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.8},
  URN =		{urn:nbn:de:0030-drops-183585},
  doi =		{10.4230/LIPIcs.SEA.2023.8},
  annote =	{Keywords: sorting, algorithms, randomization, experimentation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2022.9
Efficient Exact Learning Algorithms for Road Networks and Other Graphs with Bounded Clustering Degrees

Authors: Ramtin Afshar, Michael T. Goodrich, and Evrim Ozel

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
The completeness of road network data is significant in the quality of various routing services and applications. We introduce an efficient randomized algorithm for exact learning of road networks using simple distance queries, which can find missing roads and improve the quality of routing services. The efficiency of our algorithm depends on a cluster degree parameter, d_max, which is an upper bound on the degrees of vertex clusters defined during our algorithm. Unfortunately, we leave open the problem of theoretically bounding d_max, although we conjecture that d_max is small for road networks and other similar types of graphs. We support this conjecture by experimentally evaluating our algorithm on road network data for the U.S. and 5 European countries of various sizes. This analysis provides experimental evidence that our algorithm issues a quasilinear number of queries in expectation for road networks and similar graphs.
Cite as

Ramtin Afshar, Michael T. Goodrich, and Evrim Ozel. Efficient Exact Learning Algorithms for Road Networks and Other Graphs with Bounded Clustering Degrees. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.SEA.2022.9,
  author =	{Afshar, Ramtin and Goodrich, Michael T. and Ozel, Evrim},
  title =	{{Efficient Exact Learning Algorithms for Road Networks and Other Graphs with Bounded Clustering Degrees}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.9},
  URN =		{urn:nbn:de:0030-drops-165432},
  doi =		{10.4230/LIPIcs.SEA.2022.9},
  annote =	{Keywords: Road Networks, Exact Learning, Graph Reconstruction, Randomized Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.4
Mapping Networks via Parallel kth-Hop Traceroute Queries

Authors: Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
For a source node, v, and target node, w, the traceroute command iteratively issues "kth-hop" queries, for k = 1, 2, … , δ(v,w), which return the name of the kth vertex on a shortest path from v to w, where δ(v,w) is the distance between v and w, that is, the number of edges in a shortest-path from v to w. The traceroute command is often used for network mapping applications, the study of the connectivity of networks, and it has been studied theoretically with respect to biases it introduces for network mapping when only a subset of nodes in the network can be the source of traceroute queries. In this paper, we provide efficient network mapping algorithms, that are based on kth-hop traceroute queries. Our results include an algorithm that runs in a constant number of parallel rounds with a subquadratic number of queries under reasonable assumptions about the sampling coverage of the nodes that may issue kth-hop traceroute queries. In addition, we introduce a number of new algorithmic techniques, including a high-probability parametric parallelization of a graph clustering technique of Thorup and Zwick, which may be of independent interest.
Cite as

Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Mapping Networks via Parallel kth-Hop Traceroute Queries. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.STACS.2022.4,
  author =	{Afshar, Ramtin and Goodrich, Michael T. and Matias, Pedro and Osegueda, Martha C.},
  title =	{{Mapping Networks via Parallel kth-Hop Traceroute Queries}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{4:1--4:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.4},
  URN =		{urn:nbn:de:0030-drops-158142},
  doi =		{10.4230/LIPIcs.STACS.2022.4},
  annote =	{Keywords: Network mapping, graph algorithms, parallel algorithms, distributed computing, query complexity, kth-hop queries}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.3
Reconstructing Biological and Digital Phylogenetic Trees in Parallel

Authors: Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
In this paper, we study the parallel query complexity of reconstructing biological and digital phylogenetic trees from simple queries involving their nodes. This is motivated from computational biology, data protection, and computer security settings, which can be abstracted in terms of two parties, a responder, Alice, who must correctly answer queries of a given type regarding a degree-d tree, T, and a querier, Bob, who issues batches of queries, with each query in a batch being independent of the others, so as to eventually infer the structure of T. We show that a querier can efficiently reconstruct an n-node degree-d tree, T, with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries, including relative-distance queries and path queries. Our results are all asymptotically optimal and improve the asymptotic (sequential) query complexity for one of the problems we study. Moreover, through an experimental analysis using both real-world and synthetic data, we provide empirical evidence that our algorithms provide significant parallel speedups while also improving the total query complexities for the problems we study.
Cite as

Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing Biological and Digital Phylogenetic Trees in Parallel. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.ESA.2020.3,
  author =	{Afshar, Ramtin and Goodrich, Michael T. and Matias, Pedro and Osegueda, Martha C.},
  title =	{{Reconstructing Biological and Digital Phylogenetic Trees in Parallel}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.3},
  URN =		{urn:nbn:de:0030-drops-128696},
  doi =		{10.4230/LIPIcs.ESA.2020.3},
  annote =	{Keywords: Tree Reconstruction, Parallel Algorithms, Privacy, Phylogenetic Trees, Data Structures, Hierarchical Clustering}
}
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.ESA.2019.19
Computing k-Modal Embeddings of Planar Digraphs

Authors: Juan José Besa, Giordano Da Lozzo, and Michael T. Goodrich

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Given a planar digraph G and a positive even integer k, an embedding of G in the plane is k-modal, if every vertex of G is incident to at most k pairs of consecutive edges with opposite orientations, i.e., the incoming and the outgoing edges at each vertex are grouped by the embedding into at most k sets of consecutive edges with the same orientation. In this paper, we study the k-Modality problem, which asks for the existence of a k-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks. First, since the 2-Modality problem can be easily solved in linear time, we consider the general k-Modality problem for any value of k>2 and show that the problem is NP-complete for planar digraphs of maximum degree Delta <= k+3. We relate its computational complexity to that of two notions of planarity for flat clustered networks: Planar Intersection-Link and Planar NodeTrix representations. This allows us to answer in the strongest possible way an open question by Di Giacomo [https://doi.org/10.1007/978-3-319-73915-1_37], concerning the complexity of constructing planar NodeTrix representations of flat clustered networks with small clusters, and to address a research question by Angelini et al. [https://doi.org/10.7155/jgaa.00437], concerning intersection-link representations based on geometric objects that determine complex arrangements. On the positive side, we provide a simple FPT algorithm for partial 2-trees of arbitrary degree, whose running time is exponential in k and linear in the input size. Second, motivated by the recently-introduced planar L-drawings of planar digraphs [https://doi.org/10.1007/978-3-319-73915-1_36], which require the computation of a 4-modal embedding, we focus our attention on k=4. On the algorithmic side, we show a complexity dichotomy for the 4-Modality problem with respect to Delta, by providing a linear-time algorithm for planar digraphs with Delta <= 6. This algorithmic result is based on decomposing the input digraph into its blocks via BC-trees and each of these blocks into its triconnected components via SPQR-trees. In particular, we are able to show that the constraints imposed on the embedding by the rigid triconnected components can be tackled by means of a small set of reduction rules and discover that the algorithmic core of the problem lies in special instances of NAESAT, which we prove to be always NAE-satisfiable - a result of independent interest that improves on Porschen et al. [https://doi.org/10.1007/978-3-540-24605-3_14]. Finally, on the combinatorial side, we consider outerplanar digraphs and show that any such a digraph always admits a k-modal embedding with k=4 and that this value of k is best possible for the digraphs in this family.
Cite as

Juan José Besa, Giordano Da Lozzo, and Michael T. Goodrich. Computing k-Modal Embeddings of Planar Digraphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.ESA.2019.19,
  author =	{Besa, Juan Jos\'{e} and Da Lozzo, Giordano and Goodrich, Michael T.},
  title =	{{Computing k-Modal Embeddings of Planar Digraphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.19},
  URN =		{urn:nbn:de:0030-drops-111404},
  doi =		{10.4230/LIPIcs.ESA.2019.19},
  annote =	{Keywords: Modal Embeddings, Planarity, Directed Graphs, SPQR trees, NAESAT}
}
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
DOI: 10.4230/LIPIcs.ESA.2017.33
The Online House Numbering Problem: Min-Max Online List Labeling

Authors: William E. Devanny, Jeremy T. Fineman, Michael T. Goodrich, and Tsvi Kopelowitz

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We introduce and study the online house numbering problem, where houses are added arbitrarily along a road and must be assigned labels to maintain their ordering along the road. The online house numbering problem is related to classic online list labeling problems, except that the optimization goal here is to minimize the maximum number of times that any house is relabeled. We provide several algorithms that achieve interesting tradeoffs between upper bounds on the number of maximum relabels per element and the number of bits used by labels.
Cite as

William E. Devanny, Jeremy T. Fineman, Michael T. Goodrich, and Tsvi Kopelowitz. The Online House Numbering Problem: Min-Max Online List Labeling. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{devanny_et_al:LIPIcs.ESA.2017.33,
  author =	{Devanny, William E. and Fineman, Jeremy T. and Goodrich, Michael T. and Kopelowitz, Tsvi},
  title =	{{The Online House Numbering Problem: Min-Max Online List Labeling}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.33},
  URN =		{urn:nbn:de:0030-drops-78831},
  doi =		{10.4230/LIPIcs.ESA.2017.33},
  annote =	{Keywords: house numbering, list labeling, file maintenance}
}
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}
}

Goodrich, Michael

Document
DOI: 10.4230/DagSemRep.233
Computational Geometry (Dagstuhl Seminar 99102)

Authors: Michael Goodrich, Rolf Klein, and Raimund Seidel

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Michael Goodrich, Rolf Klein, and Raimund Seidel. Computational Geometry (Dagstuhl Seminar 99102). Dagstuhl Seminar Report 233, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{goodrich_et_al:DagSemRep.233,
  author =	{Goodrich, Michael and Klein, Rolf and Seidel, Raimund},
  title =	{{Computational Geometry (Dagstuhl Seminar 99102)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{233},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.233},
  URN =		{urn:nbn:de:0030-drops-151191},
  doi =		{10.4230/DagSemRep.233},
}
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 About DROPS Imprint Privacy Contact