10 Search Results for "Felsner, Stefan"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.17
An Extension Theorem for Signotopes

Authors: Helena Bergold, Stefan Felsner, and Manfred Scheucher

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

Abstract
In 1926, Levi showed that, for every pseudoline arrangement 𝒜 and two points in the plane, 𝒜 can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in ℝ^d with a hyperplane containing d prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in ℝ³ which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks r ≥ 4 there exist signotopes which are not extendable for two prescribed points. Our conjecture is supported by examples in ranks 4, 6, 8, 10, and 12 that were found with a SAT based approach.
Cite as

Helena Bergold, Stefan Felsner, and Manfred Scheucher. An Extension Theorem for Signotopes. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergold_et_al:LIPIcs.SoCG.2023.17,
  author =	{Bergold, Helena and Felsner, Stefan and Scheucher, Manfred},
  title =	{{An Extension Theorem for Signotopes}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{17:1--17:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.17},
  URN =		{urn:nbn:de:0030-drops-178676},
  doi =		{10.4230/LIPIcs.SoCG.2023.17},
  annote =	{Keywords: arrangement of pseudolines, extendability, Levi’s extension lemma, arrangement of pseudohyperplanes, signotope, oriented matroid, partial order, Boolean satisfiability (SAT)}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.31
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-dev.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
DOI: 10.4230/LIPIcs.SoCG.2022.39
Weak Coloring Numbers of Intersection Graphs

Authors: Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for a positive integer k, we seek a vertex ordering such that every vertex can (weakly respectively strongly) reach in k steps only few vertices that precede it in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in structural and algorithmic graph theory. Recently, Dvořák, McCarty, and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in ℝ^d, such as homothets of a compact convex object, or comparable axis-aligned boxes. In this paper, we prove upper and lower bounds for the k-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in k, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).
Cite as

Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky. Weak Coloring Numbers of Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.39,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Pek\'{a}rek, Jakub and Ueckerdt, Torsten and Yuditsky, Yelena},
  title =	{{Weak Coloring Numbers of Intersection Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.39},
  URN =		{urn:nbn:de:0030-drops-160477},
  doi =		{10.4230/LIPIcs.SoCG.2022.39},
  annote =	{Keywords: geometric intersection graphs, weak and strong coloring numbers}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.23
Reconfiguring Independent Sets on Interval Graphs

Authors: Marcin Briański, Stefan Felsner, Jędrzej Hodor, and Piotr Micek

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size k are reconfigurable in an n-vertex interval graph, then there is a reconfiguration sequence of length 𝒪(k⋅ n²). We also provide a construction in which the shortest reconfiguration sequence is of length Ω(k²⋅ n). As a counterpart to these results, we also establish that Independent Set Reconfiguration is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.
Cite as

Marcin Briański, Stefan Felsner, Jędrzej Hodor, and Piotr Micek. Reconfiguring Independent Sets on Interval Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brianski_et_al:LIPIcs.MFCS.2021.23,
  author =	{Bria\'{n}ski, Marcin and Felsner, Stefan and Hodor, J\k{e}drzej and Micek, Piotr},
  title =	{{Reconfiguring Independent Sets on Interval Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.23},
  URN =		{urn:nbn:de:0030-drops-144633},
  doi =		{10.4230/LIPIcs.MFCS.2021.23},
  annote =	{Keywords: reconfiguration, independent sets, interval graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.29
Dual Circumference and Collinear Sets

Authors: Vida Dujmović and Pat Morin

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

Abstract
We show that, if an n-vertex triangulation T of maximum degree Delta has a dual that contains a cycle of length l, then T has a non-crossing straight-line drawing in which some set, called a collinear set, of Omega(l/Delta^4) vertices lie on a line. Using the current lower bounds on the length of longest cycles in 3-regular 3-connected graphs, this implies that every n-vertex planar graph of maximum degree Delta has a collinear set of size Omega(n^{0.8}/Delta^4). Very recently, Dujmović et al. (SODA 2019) showed that, if S is a collinear set in a triangulation T then, for any point set X subset R^2 with |X|=|S|, T has a non-crossing straight-line drawing in which the vertices of S are drawn on the points in X. Because of this, collinear sets have numerous applications in graph drawing and related areas.
Cite as

Vida Dujmović and Pat Morin. Dual Circumference and Collinear Sets. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dujmovic_et_al:LIPIcs.SoCG.2019.29,
  author =	{Dujmovi\'{c}, Vida and Morin, Pat},
  title =	{{Dual Circumference and Collinear Sets}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{29:1--29: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.29},
  URN =		{urn:nbn:de:0030-drops-104338},
  doi =		{10.4230/LIPIcs.SoCG.2019.29},
  annote =	{Keywords: Planar graphs, collinear sets, untangling, column planarity, universal point subsets, partial simultaneous geometric drawings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.38
The Crossing Tverberg Theorem

Authors: Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner

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

Abstract
The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.
Cite as

Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fulek_et_al:LIPIcs.SoCG.2019.38,
  author =	{Fulek, Radoslav and G\"{a}rtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli},
  title =	{{The Crossing Tverberg Theorem}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{38:1--38:13},
  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.38},
  URN =		{urn:nbn:de:0030-drops-104423},
  doi =		{10.4230/LIPIcs.SoCG.2019.38},
  annote =	{Keywords: Discrete geometry, Tverberg theorem, Crossing Tverberg theorem}
}
Document
DOI: 10.4230/OASIcs.SOSA.2019.8
On Primal-Dual Circle Representations

Authors: Stefan Felsner and Günter Rote

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
The Koebe-Andreev-Thurston Circle Packing Theorem states that every triangulated planar graph has a contact representation by circles. The theorem has been generalized in various ways. The most prominent generalization assures the existence of a primal-dual circle representation for every 3-connected planar graph. We present a simple and elegant elementary proof of this result.
Cite as

Stefan Felsner and Günter Rote. On Primal-Dual Circle Representations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:OASIcs.SOSA.2019.8,
  author =	{Felsner, Stefan and Rote, G\"{u}nter},
  title =	{{On Primal-Dual Circle Representations}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{8:1--8:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.8},
  URN =		{urn:nbn:de:0030-drops-100349},
  doi =		{10.4230/OASIcs.SOSA.2019.8},
  annote =	{Keywords: Disk packing, planar graphs, contact representation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.38
Rainbow Cycles in Flip Graphs

Authors: Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
The flip graph of triangulations has as vertices all triangulations of a convex n-gon, and an edge between any two triangulations that differ in exactly one edge. An r-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly r times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of r-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex n-gon, the flip graph of plane spanning trees on an arbitrary set of n points, and the flip graph of non-crossing perfect matchings on a set of n points in convex position. In addition, we consider two flip graphs on classes of non-geometric objects: the flip graph of permutations of {1,2,...,n } and the flip graph of k-element subsets of {1,2,...,n }. In each of the five settings, we prove the existence and non-existence of rainbow cycles for different values of r, n and k.
Cite as

Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering. Rainbow Cycles in Flip Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SoCG.2018.38,
  author =	{Felsner, Stefan and Kleist, Linda and M\"{u}tze, Torsten and Sering, Leon},
  title =	{{Rainbow Cycles in Flip Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.38},
  URN =		{urn:nbn:de:0030-drops-87514},
  doi =		{10.4230/LIPIcs.SoCG.2018.38},
  annote =	{Keywords: flip graph, cycle, rainbow, Gray code, triangulation, spanning tree, matching, permutation, subset, combination}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.37
Strongly Monotone Drawings of Planar Graphs

Authors: Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze, and Manfred Scheucher

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

Abstract
A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.
Cite as

Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze, and Manfred Scheucher. Strongly Monotone Drawings of Planar Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SoCG.2016.37,
  author =	{Felsner, Stefan and Igamberdiev, Alexander and Kindermann, Philipp and Klemz, Boris and Mchedlidze, Tamara and Scheucher, Manfred},
  title =	{{Strongly Monotone Drawings of Planar Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{37:1--37:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.37},
  URN =		{urn:nbn:de:0030-drops-59292},
  doi =		{10.4230/LIPIcs.SoCG.2016.37},
  annote =	{Keywords: graph drawing, planar graphs, strongly monotone, strictly convex, primal-dual circle packing}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.630
On-line Coloring between Two Lines

Authors: Stefan Felsner, Piotr Micek, and Torsten Ueckerdt

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

Abstract
We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axis-aligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an on-line algorithm coloring graphs given by convex sets between two lines that uses O(w^3) colors on graphs with maximum clique size w. In contrast intersection graphs of segments attached to a single line may force any on-line coloring algorithm to use an arbitrary number of colors even when w=2. The left-of relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class C of posets obtained from convex sets between two lines with some other classes of posets: all 2-dimensional posets and all posets of height 2 are in C but there is a 3-dimensional poset of height 3 that does not belong to C. We also show that the on-line coloring problem for curves between two lines is as hard as the on-line chain partition problem for arbitrary posets.
Cite as

Stefan Felsner, Piotr Micek, and Torsten Ueckerdt. On-line Coloring between Two Lines. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 630-641, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SOCG.2015.630,
  author =	{Felsner, Stefan and Micek, Piotr and Ueckerdt, Torsten},
  title =	{{On-line Coloring between Two Lines}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{630--641},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.630},
  URN =		{urn:nbn:de:0030-drops-50915},
  doi =		{10.4230/LIPIcs.SOCG.2015.630},
  annote =	{Keywords: intersection graphs, cocomparability graphs, on-line coloring}
}
  • Refine by Author
  • 7 Felsner, Stefan
  • 2 Micek, Piotr
  • 2 Scheucher, Manfred
  • 2 Ueckerdt, Torsten
  • 1 Bergold, Helena
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Graph theory
  • 3 Theory of computation → Computational geometry
  • 2 Human-centered computing → Graph drawings
  • 2 Mathematics of computing → Combinatoric problems
  • 1 Hardware → Theorem proving and SAT solving
  • Show More...

  • Refine by Keyword
  • 2 planar graphs
  • 1 2-page book embedding
  • 1 2-tree
  • 1 Boolean satisfiability (SAT)
  • 1 Crossing Tverberg theorem
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 3 2019
  • 2 2023
  • 1 2015
  • 1 2016
  • 1 2018
  • Show More...

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