Search Results

Documents authored by Schulz, André

Found 3 Possible Name Variants:

Schulz, Andreas S.

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.25
Robust Appointment Scheduling with Heterogeneous Costs

Authors: Andreas S. Schulz and Rajan Udwani

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Designing simple appointment systems that under uncertainty in service times, try to achieve both high utilization of expensive medical equipment and personnel as well as short waiting time for patients, has long been an interesting and challenging problem in health care. We consider a robust version of the appointment scheduling problem, introduced by Mittal et al. (2014), with the goal of finding simple and easy-to-use algorithms. Previous work focused on the special case where per-unit costs due to under-utilization of equipment/personnel are homogeneous i.e., costs are linear and identical. We consider the heterogeneous case and devise an LP that has a simple closed-form solution. This solution yields the first constant-factor approximation for the problem. We also find special cases beyond homogeneous costs where the LP leads to closed form optimal schedules. Our approach and results extend more generally to convex piece-wise linear costs. For the case where the order of patients is changeable, we focus on linear costs and show that the problem is strongly NP-hard when the under-utilization costs are heterogeneous. For changeable order with homogeneous under-utilization costs, it was previously shown that an EPTAS exists. We instead find an extremely simple, ratio-based ordering that is 1.0604 approximate.
Cite as

Andreas S. Schulz and Rajan Udwani. Robust Appointment Scheduling with Heterogeneous Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schulz_et_al:LIPIcs.APPROX-RANDOM.2019.25,
  author =	{Schulz, Andreas S. and Udwani, Rajan},
  title =	{{Robust Appointment Scheduling with Heterogeneous Costs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.25},
  URN =		{urn:nbn:de:0030-drops-112407},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.25},
  annote =	{Keywords: Appointment scheduling, approximation algorithms, robust optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.74
Min-Sum Scheduling Under Precedence Constraints

Authors: Andreas S. Schulz and José Verschae

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In many scheduling situations, it is important to consider non-linear functions of job completions times in the objective. This was already recognized by Smith (1956). Recently, the theory community has begun a thorough study of the resulting problems, mostly on single-machine instances for which all permutations of jobs are feasible. However, a typical feature of many scheduling problems is that some jobs can only be processed after others. In this paper, we give the first approximation algorithms for min-sum scheduling with (nonnegative, non-decreasing) non-linear functions and general precedence constraints. In particular, for 1|prec|sum w_j f(C_j), we propose a polynomial-time universal algorithm that performs well for all functions f simultaneously. Its approximation guarantee is 2 for all concave functions, at worst. We also provide a (non-universal) polynomial-time algorithm for the more general case 1|prec|sum f_j(C_j). The performance guarantee is no worse than 2+epsilon for all concave functions. Our results match the best bounds known for the case of linear functions, a widely studied problem, and considerably extend the results for minimizing sum w_jf(C_j) without precedence constraints.
Cite as

Andreas S. Schulz and José Verschae. Min-Sum Scheduling Under Precedence Constraints. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 74:1-74:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{schulz_et_al:LIPIcs.ESA.2016.74,
  author =	{Schulz, Andreas S. and Verschae, Jos\'{e}},
  title =	{{Min-Sum Scheduling Under Precedence Constraints}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{74:1--74:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.74},
  URN =		{urn:nbn:de:0030-drops-64157},
  doi =		{10.4230/LIPIcs.ESA.2016.74},
  annote =	{Keywords: scheduling, approximation algorithms, linear programming relaxations, precedence constraints}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.356
Robust Appointment Scheduling

Authors: Shashi Mittal, Andreas S. Schulz, and Sebastian Stiller

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
Health care providers are under tremendous pressure to reduce costs and increase quality of their services. It has long been recognized that well-designed appointment systems have the potential to improve utilization of expensive personnel and medical equipment and to reduce waiting times for patients. In a widely influential survey on outpatient scheduling, Cayirli and Veral (2003) concluded that the "biggest challenge for future research will be to develop easy-to-use heuristics." We analyze the appointment scheduling problem from a robust-optimization perspective, and we establish the existence of a closed-form optimal solution--arguably the simplest and best `heuristic' possible. In case the order of patients is changeable, the robust optimization approach yields a novel formulation of the appointment scheduling problem as that of minimizing a concave function over a supermodular polyhedron. We devise the first constant-factor approximation algorithm for this case.
Cite as

Shashi Mittal, Andreas S. Schulz, and Sebastian Stiller. Robust Appointment Scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 356-370, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mittal_et_al:LIPIcs.APPROX-RANDOM.2014.356,
  author =	{Mittal, Shashi and Schulz, Andreas S. and Stiller, Sebastian},
  title =	{{Robust Appointment Scheduling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{356--370},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.356},
  URN =		{urn:nbn:de:0030-drops-47089},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.356},
  annote =	{Keywords: Robust Optimization, Health Care Scheduling, Approximation Algorithms}
}
Document
DOI: 10.4230/DagSemProc.09261.27
Sharing Supermodular Costs

Authors: Andreas S. Schulz and Nelson A. Uhan

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
We apply ideas from cooperative game theory to study situations in which a set of agents face supermodular costs. These situations appear in a variety of scheduling contexts, as well as in some settings related to facility location and network design. Intuitively, cooperation amongst rational agents who face supermodular costs is unlikely. However, in circumstances where the failure to cooperate may lead to negative externalities, one might be interested in methods of encouraging cooperation. The least core value of a cooperative game is the minimum penalty we need to charge a coalition for acting independently that encourages cooperation by ensuring the existence of an efficient and stable cost allocation. The set of all such cost allocations is called the least core. In this work, we study the computational complexity and approximability of computing the least core value of supermodular cost cooperative games. We show that computing the least core value of supermodular cost cooperative games is strongly NP-hard, and build a framework to approximate the least core value of these games using oracles that approximately determine maximally violated constraints. This framework yields a $(3+epsilon)$-approximation algorithm for computing the least core value of supermodular cost cooperative games. As a by-product, we show how to compute accompanying approximate least core cost allocations for these games. We also apply our approximation framework to obtain better results for two particular classes of supermodular cost cooperative games that arise from scheduling and matroid optimization.
Cite as

Andreas S. Schulz and Nelson A. Uhan. Sharing Supermodular Costs. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{schulz_et_al:DagSemProc.09261.27,
  author =	{Schulz, Andreas S. and Uhan, Nelson A.},
  title =	{{Sharing Supermodular Costs}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.27},
  URN =		{urn:nbn:de:0030-drops-21702},
  doi =		{10.4230/DagSemProc.09261.27},
  annote =	{Keywords: Cooperative games, approximation algorithms, algorithmic game theory}
}
Document
DOI: 10.4230/DagSemProc.05031.18
New Old Algorithms for Stochastic Scheduling

Authors: Andreas S. Schulz

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
We consider the stochastic identical parallel machine scheduling problem and its online extension, when the objective is to minimize the expected total weighted completion time of a set of jobs that are released over time. We give randomized as well as deterministic online and offline algorithms that have the best known performance guarantees in either setting, online or offline and deterministic or randomized. Our analysis is based on a novel linear programming relaxation for stochastic scheduling problems that can be solved online.
Cite as

Andreas S. Schulz. New Old Algorithms for Stochastic Scheduling. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{schulz:DagSemProc.05031.18,
  author =	{Schulz, Andreas S.},
  title =	{{New Old Algorithms for Stochastic Scheduling}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.18},
  URN =		{urn:nbn:de:0030-drops-1931},
  doi =		{10.4230/DagSemProc.05031.18},
  annote =	{Keywords: stochastic scheduling , online algorithms , competitive analysis , approximation algorithms , linear programming relaxations}
}

Schulz, Andre

Document
DOI: 10.4230/LIPIcs.SoCG.2023.44
On the Geometric Thickness of 2-Degenerate Graphs

Authors: Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz

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

Abstract
A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any straight-line drawing with a decomposition of the edge set into 2 plane graphs. That is, there are 2-degenerate graphs with geometric thickness, and hence geometric arboricity, at least 3. This answers two questions posed by Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004].
Cite as

Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz. On the Geometric Thickness of 2-Degenerate Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.SoCG.2023.44,
  author =	{Jain, Rahul and Ricci, Marco and Rollin, Jonathan and Schulz, Andr\'{e}},
  title =	{{On the Geometric Thickness of 2-Degenerate Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{44:1--44:15},
  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.44},
  URN =		{urn:nbn:de:0030-drops-178946},
  doi =		{10.4230/LIPIcs.SoCG.2023.44},
  annote =	{Keywords: Degeneracy, geometric thickness, geometric arboricity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.11
Adjacency Graphs of Polyhedral Surfaces

Authors: Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff

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

Abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
Cite as

Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11,
  author =	{Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander},
  title =	{{Adjacency Graphs of Polyhedral Surfaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-138107},
  doi =		{10.4230/LIPIcs.SoCG.2021.11},
  annote =	{Keywords: polyhedral complexes, realizability, contact representation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.79
Recognizing Planar Laman Graphs

Authors: Jonathan Rollin, Lena Schlipf, and André Schulz

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

Abstract
Laman graphs are the minimally rigid graphs in the plane. We present two algorithms for recognizing planar Laman graphs. A simple algorithm with running time O(n^(3/2)) and a more complicated algorithm with running time O(n log^3 n) based on involved planar network flow algorithms. Both improve upon the previously fastest algorithm for general graphs by Gabow and Westermann [Algorithmica, 7(5-6):465 - 497, 1992] with running time O(n sqrt{n log n}). To solve this problem we introduce two algorithms (with the running times stated above) that check whether for a directed planar graph G, disjoint sets S, T subseteq V(G), and a fixed k the following connectivity condition holds: for each vertex s in S there are k directed paths from s to T pairwise having only vertex s in common. This variant of connectivity seems interesting on its own.
Cite as

Jonathan Rollin, Lena Schlipf, and André Schulz. Recognizing Planar Laman Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 79:1-79:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rollin_et_al:LIPIcs.ESA.2019.79,
  author =	{Rollin, Jonathan and Schlipf, Lena and Schulz, Andr\'{e}},
  title =	{{Recognizing Planar Laman Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{79:1--79:12},
  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.79},
  URN =		{urn:nbn:de:0030-drops-112001},
  doi =		{10.4230/LIPIcs.ESA.2019.79},
  annote =	{Keywords: planar graphs, Laman graphs, network flow, connectivity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.269
Algorithms for Designing Pop-Up Cards

Authors: Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°.
Cite as

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow. Algorithms for Designing Pop-Up Cards. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.STACS.2013.269,
  author =	{Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lubiw, Anna and Schulz, Andr\'{e} and Souvaine, Diane L. and Viglietta, Giovanni and Winslow, Andrew},
  title =	{{Algorithms for Designing Pop-Up Cards}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{269--280},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.269},
  URN =		{urn:nbn:de:0030-drops-39407},
  doi =		{10.4230/LIPIcs.STACS.2013.269},
  annote =	{Keywords: geometric folding, linkages, universality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.637
Bounds on the maximum multiplicity of some common geometric graphs

Authors: Adrian Dumitrescu, Andre Schulz, Adam Sheffer, and Csaba D. Toth

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We obtain new lower and upper bounds for the maximum multiplicity of some weighted, and respectively non-weighted, common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Omega (8.65^n) different triangulations. This improves the bound Omega (8.48^n) achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We present a new lower bound of Omega(11.97^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Omega(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.664^n) non-crossing spanning cycles. (iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(n log n) time algorithm for computing them.
Cite as

Adrian Dumitrescu, Andre Schulz, Adam Sheffer, and Csaba D. Toth. Bounds on the maximum multiplicity of some common geometric graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 637-648, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.STACS.2011.637,
  author =	{Dumitrescu, Adrian and Schulz, Andre and Sheffer, Adam and Toth, Csaba D.},
  title =	{{Bounds on the maximum multiplicity of some common geometric graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{637--648},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.637},
  URN =		{urn:nbn:de:0030-drops-30505},
  doi =		{10.4230/LIPIcs.STACS.2011.637},
  annote =	{Keywords: combinatorial geometry, matching, triangulation, spanning tree, spanning cycle, weighted structure, non-crossing condition}
}

Schulz, André

Document
DOI: 10.4230/LIPIcs.SoCG.2023.44
On the Geometric Thickness of 2-Degenerate Graphs

Authors: Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz

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

Abstract
A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any straight-line drawing with a decomposition of the edge set into 2 plane graphs. That is, there are 2-degenerate graphs with geometric thickness, and hence geometric arboricity, at least 3. This answers two questions posed by Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004].
Cite as

Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz. On the Geometric Thickness of 2-Degenerate Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.SoCG.2023.44,
  author =	{Jain, Rahul and Ricci, Marco and Rollin, Jonathan and Schulz, Andr\'{e}},
  title =	{{On the Geometric Thickness of 2-Degenerate Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{44:1--44:15},
  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.44},
  URN =		{urn:nbn:de:0030-drops-178946},
  doi =		{10.4230/LIPIcs.SoCG.2023.44},
  annote =	{Keywords: Degeneracy, geometric thickness, geometric arboricity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.11
Adjacency Graphs of Polyhedral Surfaces

Authors: Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff

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

Abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
Cite as

Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11,
  author =	{Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander},
  title =	{{Adjacency Graphs of Polyhedral Surfaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-138107},
  doi =		{10.4230/LIPIcs.SoCG.2021.11},
  annote =	{Keywords: polyhedral complexes, realizability, contact representation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.79
Recognizing Planar Laman Graphs

Authors: Jonathan Rollin, Lena Schlipf, and André Schulz

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

Abstract
Laman graphs are the minimally rigid graphs in the plane. We present two algorithms for recognizing planar Laman graphs. A simple algorithm with running time O(n^(3/2)) and a more complicated algorithm with running time O(n log^3 n) based on involved planar network flow algorithms. Both improve upon the previously fastest algorithm for general graphs by Gabow and Westermann [Algorithmica, 7(5-6):465 - 497, 1992] with running time O(n sqrt{n log n}). To solve this problem we introduce two algorithms (with the running times stated above) that check whether for a directed planar graph G, disjoint sets S, T subseteq V(G), and a fixed k the following connectivity condition holds: for each vertex s in S there are k directed paths from s to T pairwise having only vertex s in common. This variant of connectivity seems interesting on its own.
Cite as

Jonathan Rollin, Lena Schlipf, and André Schulz. Recognizing Planar Laman Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 79:1-79:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rollin_et_al:LIPIcs.ESA.2019.79,
  author =	{Rollin, Jonathan and Schlipf, Lena and Schulz, Andr\'{e}},
  title =	{{Recognizing Planar Laman Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{79:1--79:12},
  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.79},
  URN =		{urn:nbn:de:0030-drops-112001},
  doi =		{10.4230/LIPIcs.ESA.2019.79},
  annote =	{Keywords: planar graphs, Laman graphs, network flow, connectivity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.269
Algorithms for Designing Pop-Up Cards

Authors: Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°.
Cite as

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow. Algorithms for Designing Pop-Up Cards. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.STACS.2013.269,
  author =	{Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lubiw, Anna and Schulz, Andr\'{e} and Souvaine, Diane L. and Viglietta, Giovanni and Winslow, Andrew},
  title =	{{Algorithms for Designing Pop-Up Cards}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{269--280},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.269},
  URN =		{urn:nbn:de:0030-drops-39407},
  doi =		{10.4230/LIPIcs.STACS.2013.269},
  annote =	{Keywords: geometric folding, linkages, universality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.637
Bounds on the maximum multiplicity of some common geometric graphs

Authors: Adrian Dumitrescu, Andre Schulz, Adam Sheffer, and Csaba D. Toth

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We obtain new lower and upper bounds for the maximum multiplicity of some weighted, and respectively non-weighted, common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Omega (8.65^n) different triangulations. This improves the bound Omega (8.48^n) achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We present a new lower bound of Omega(11.97^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Omega(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.664^n) non-crossing spanning cycles. (iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(n log n) time algorithm for computing them.
Cite as

Adrian Dumitrescu, Andre Schulz, Adam Sheffer, and Csaba D. Toth. Bounds on the maximum multiplicity of some common geometric graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 637-648, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.STACS.2011.637,
  author =	{Dumitrescu, Adrian and Schulz, Andre and Sheffer, Adam and Toth, Csaba D.},
  title =	{{Bounds on the maximum multiplicity of some common geometric graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{637--648},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.637},
  URN =		{urn:nbn:de:0030-drops-30505},
  doi =		{10.4230/LIPIcs.STACS.2011.637},
  annote =	{Keywords: combinatorial geometry, matching, triangulation, spanning tree, spanning cycle, weighted structure, non-crossing condition}
}
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