Felsner, Stefan ;
Micek, Piotr ;
Ueckerdt, Torsten
Online Coloring between Two Lines
Abstract
We study online 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 (axisaligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an online 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 online coloring algorithm to use an arbitrary number of colors even when w=2.
The leftof 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 2dimensional posets and all posets of height 2 are in C but there is a 3dimensional poset of height 3 that does not belong to C.
We also show that the online coloring problem for curves between two lines is as hard as the online chain partition problem for arbitrary posets.
BibTeX  Entry
@InProceedings{felsner_et_al:LIPIcs:2015:5091,
author = {Stefan Felsner and Piotr Micek and Torsten Ueckerdt},
title = {{Online Coloring between Two Lines}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {630641},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5091},
URN = {urn:nbn:de:0030drops50915},
doi = {10.4230/LIPIcs.SOCG.2015.630},
annote = {Keywords: intersection graphs, cocomparability graphs, online coloring}
}
12.06.2015
Keywords: 

intersection graphs, cocomparability graphs, online coloring 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

12.06.2015 