Line arrangements and geometric graph classes
Tobias Müller · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2010
Integer representations of unit square graphsTheorem.[Czyzowicz et al, 1997] Intersection graphs of same-size squares can be represented with all corner points on a O(n 2 ) × O(n 2 )-grid. Concluding remarksStoring coordinates is maybe not such a good idea.Open problem: Find a more clever way to "encode the geometry". Concluding remarksStoring coordinates is maybe not such a good idea.Open problem: Find a more clever way to "encode the geometry".Open problem: membership in NP of recognition problems for disk / unit disk / segment / dot product graphs.(This will show that "existential theory of the reals" is in NP also.) Concluding remarksStoring coordinates is maybe not such a good idea.Open problem: Find a more clever way to "encode the geometry".Open problem: membership in NP of recognition problems for disk / unit disk / segment / dot product graphs.(This will show that "existential theory of the reals" is in NP also.)Further work: carry out same programme for other geometric graph classes. Concluding remarksStoring coordinates is maybe not such a good idea.Open problem: Find a more clever way to "encode the geometry".Open problem: membership in NP of recognition problems for disk / unit disk / segment / dot product graphs.(This will show that "existential theory of the reals" is in NP also.)Further work: carry out same programme for other geometric graph classes.Dot-product dimension of other graph classes.