2026-07-22T21:25:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5091 2024-03-06T10:35:55Z ddc:004 open_access

On-line Coloring between Two Lines Felsner, Stefan Micek, Piotr Ueckerdt, Torsten intersection graphs cocomparability graphs on-line coloring 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Felsner and Piotr Micek and Torsten Ueckerdt 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.630 urn:nbn:de:0030-drops-50915 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.630 eng https://creativecommons.org/licenses/by/3.0/legalcode