4 Search Results for "Förster, Henry"


Document
Linear Size Universal Point Sets for Classes of Planar Graphs

Authors: Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder, and Raphael Steiner

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


Abstract
A finite set P of points in the plane is n-universal with respect to a class 𝒞 of planar graphs if every n-vertex graph in 𝒞 admits a crossing-free straight-line drawing with vertices at points of P. For the class of all planar graphs the best known upper bound on the size of a universal point set is quadratic and the best known lower bound is linear in n. Some classes of planar graphs are known to admit universal point sets of near linear size, however, there are no truly linear bounds for interesting classes beyond outerplanar graphs. In this paper, we show that there is a universal point set of size 2n-2 for the class of bipartite planar graphs with n vertices. The same point set is also universal for the class of n-vertex planar graphs of maximum degree 3. The point set used for the results is what we call an exploding double chain, and we prove that this point set allows planar straight-line embeddings of many more planar graphs, namely of all subgraphs of planar graphs admitting a one-sided Hamiltonian cycle. The result for bipartite graphs also implies that every n-vertex plane graph has a 1-bend drawing all whose bends and vertices are contained in a specific point set of size 4n-6, this improves a bound of 6n-10 for the same problem by Löffler and Tóth.

Cite as

Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder, and Raphael Steiner. Linear Size Universal Point Sets for Classes of Planar Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SoCG.2023.31,
  author =	{Felsner, Stefan and Schrezenmaier, Hendrik and Schr\"{o}der, Felix and Steiner, Raphael},
  title =	{{Linear Size Universal Point Sets for Classes of Planar Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{31:1--31: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.31},
  URN =		{urn:nbn:de:0030-drops-178814},
  doi =		{10.4230/LIPIcs.SoCG.2023.31},
  annote =	{Keywords: Graph drawing, Universal point set, One-sided Hamiltonian, 2-page book embedding, Separating decomposition, Quadrangulation, 2-tree, Subcubic planar graph}
}
Document
On Compact RAC Drawings

Authors: Henry Förster and Michael Kaufmann

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


Abstract
We present new bounds for the required area of Right Angle Crossing (RAC) drawings for complete graphs, i.e. drawings where any two crossing edges are perpendicular to each other. First, we improve upon results by Didimo et al. [Walter Didimo et al., 2011] and Di Giacomo et al. [Emilio Di Giacomo et al., 2011] by showing how to compute a RAC drawing with three bends per edge in cubic area. We also show that quadratic area can be achieved when allowing eight bends per edge in general or with three bends per edge for p-partite graphs. As a counterpart, we prove that in general quadratic area is not sufficient for RAC drawings with three bends per edge.

Cite as

Henry Förster and Michael Kaufmann. On Compact RAC Drawings. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.ESA.2020.53,
  author =	{F\"{o}rster, Henry and Kaufmann, Michael},
  title =	{{On Compact RAC Drawings}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{53:1--53:21},
  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.53},
  URN =		{urn:nbn:de:0030-drops-129192},
  doi =		{10.4230/LIPIcs.ESA.2020.53},
  annote =	{Keywords: RAC drawings, visualization of dense graphs, compact drawings}
}
Document
Drawing Graphs with Circular Arcs and Right-Angle Crossings

Authors: Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff

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


Abstract
In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n-10 edges. We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n-12 edges and that there are n-vertex arc-RAC graphs with 4.5n - O(√n) edges.

Cite as

Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. Drawing Graphs with Circular Arcs and Right-Angle Crossings. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.SWAT.2020.21,
  author =	{Chaplick, Steven and F\"{o}rster, Henry and Kryven, Myroslav and Wolff, Alexander},
  title =	{{Drawing Graphs with Circular Arcs and Right-Angle Crossings}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-122687},
  doi =		{10.4230/LIPIcs.SWAT.2020.21},
  annote =	{Keywords: circular arcs, right-angle crossings, edge density, charging argument}
}
Document
Algorithms and Insights for RaceTrack

Authors: Michael A. Bekos, Till Bruckdorfer, Henry Förster, Michael Kaufmann, Simon Poschenrieder, and Thomas Stüber

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)


Abstract
We discuss algorithmic issues on the well-known paper-and-pencil game RaceTrack. On a very simple track called Indianapolis, we introduce the problem and simple approaches, that will be gradually refined. We present and experimentally evaluate efficient algorithms for single player scenarios. We also consider a variant where the parts of the track are known as soon as they become visible during the race.

Cite as

Michael A. Bekos, Till Bruckdorfer, Henry Förster, Michael Kaufmann, Simon Poschenrieder, and Thomas Stüber. Algorithms and Insights for RaceTrack. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.FUN.2016.6,
  author =	{Bekos, Michael A. and Bruckdorfer, Till and F\"{o}rster, Henry and Kaufmann, Michael and Poschenrieder, Simon and St\"{u}ber, Thomas},
  title =	{{Algorithms and Insights for RaceTrack}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.6},
  URN =		{urn:nbn:de:0030-drops-58818},
  doi =		{10.4230/LIPIcs.FUN.2016.6},
  annote =	{Keywords: Racetrack, State-graph, complexity}
}
  • Refine by Author
  • 3 Förster, Henry
  • 2 Kaufmann, Michael
  • 1 Bekos, Michael A.
  • 1 Bruckdorfer, Till
  • 1 Chaplick, Steven
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Graphs and surfaces
  • 2 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 1 2-page book embedding
  • 1 2-tree
  • 1 Graph drawing
  • 1 One-sided Hamiltonian
  • 1 Quadrangulation
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2020
  • 1 2016
  • 1 2023

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