research-article

Integer representations of convex polygon intersection graphs

Authors:

Tobias Müller,

Erik Jan van Leeuwen,

Jan van LeeuwenAuthors Info & Claims

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Pages 300 - 307

https://doi.org/10.1145/1998196.1998248

Published: 13 June 2011 Publication History

Abstract

We give the first lower bounds on the grid size needed to represent the intersection graphs of~convex polygons. Here each corner of a polygon in the representation must lie on a corner of the grid. We provide a series of geometric constructions showing that for intersection graphs of: translated copies of any fixed parallelogram, grids of size Ω(n²) x Ω(n²) are needed; translated copies of any other fixed convex polygon, grids of size 2^Ω(n) x 2^Ω(n) are needed; homothetic copies of any fixed convex polygon, grids of size 2^Ω(n) x 2^Ω(n) are needed.

We complement these results by giving a matching upper bound in each case. Hence we settle the complexity of the integer representation problem for these graphs. The upper bounds substantially improve earlier bounds and extend to higher dimensions.

References

[1]

D. Bienstock. Some provably hard crossing number problems. Discrete Comput. Geom., 6(5):443--459, 1991.

Digital Library

[2]

H. Breu. Algorithmic aspects of constrained unit disk graphs. PhD Thesis, The University of British Columbia, Vancouver, 1996.

Digital Library

[3]

H. Breu and D. G. Kirkpatrick. Unit disk graph recognition is NP-hard. Comput. Geom., 9(1--2):3--24, 1998.

Digital Library

[4]

J. Cerný, D. Král, H. Nyklová, and O. Pangrác. On intersection graphs of segments with prescribed slopes. In S. G. Kobourov and M. T. Goodrich, editors, Graph Drawing 2001, Proceedings Lecture Notes in Computer Science, volume 2265, pages 261--271. Springer-Verlag, Berlin, 2002.

Digital Library

[5]

B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Math., 86(1--3):165--177, 1990.

Digital Library

[6]

D. G. Corneil, H. Kim, S. Natarajan, S. Olariu, and A. P. Sprague. Simple linear time recognition of unit interval graphs. Inform. Process. Lett., 55(2):99--104, 1995.

Digital Library

[7]

J. Czyzowicz, E. Kranakis, D. Krizanc, and J. Urrutia. Discrete realizations of contact and intersection graphs. Int. J. Pure Appl. Math., 13(4):429--442, 2004.

[8]

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41--51, 1990.

[9]

G. Ehrlich, S. Even, and R. E. Tarjan. Intersection graphs of curves in the plane. J. Combinatorial Theory Ser. B, 21(1):8--20, 1976.

[10]

P. Hlinený and J. Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Math., 229(1--3):101--124, 2001.

Digital Library

[11]

M. Kaufmann, J. Kratochvíl, K. A. Lehmann, and A. Subramanian. Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition. In SODA '06, Proc. Seventheenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 832--841. ACM, 2006.

Digital Library

[12]

J. Kratochvíl. String graphs II: recognizing string graphs is NP-hard. J. Combin. Theory Ser. B, 52(1):67--78, 1991.

Digital Library

[13]

J. Kratochvíl and J. Matousek. String graphs requiring exponential representations. J. Combin. Theory Ser. B, 53(1):1--4, 1991.

Digital Library

[14]

J. Kratochvíl and J. Matousek. Intersection graphs of segments. J. Combin. Theory Ser. B, 62(2):289--315, 1994.

Digital Library

[15]

J. Kratochvíl and M. Pergel. Intersection graphs of homothetic polygons. In The International Conference on Topological and Geometric Graph Theory, volume 31 of Electron. Notes Discrete Math., pages 277--280. Elsevier Sci. B. V., Amsterdam, 2008.

[16]

C. J. H. McDiarmid and T. Müller. Integer representations of disk and segment graphs. submitted, 2010.

[17]

M. Pergel. Special graph classes and algorithms on them. PhD Thesis, Dept. of Applied Mathematics,Charles University, Prague, 2008, http://kam.mff.cuni.cz/ perm/main.pdf.

[18]

M. Schaefer. Complexity of some geometric and topological problems. In D. Eppstein and E. R. Gansner, editors, Graph Drawing 2009, Proceedings, Lecture Notes in Computer Science, volume 5849, pages 334--344. Springer-Verlag, Berlin, 2010.

Digital Library

[19]

W. Schnyder. Embedding planar graphs on the grid. In SODA '90, Proc. First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138--148. SIAM, 1990.

Digital Library

[20]

A. Schrijver. Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons Ltd., Chichester, 1986.

Digital Library

[21]

J. Spinrad. Efficient graph representations, volume 19 of Fields Institute Monographs. American Mathematical Society, Providence, RI, 2003.

[22]

E. J. van Leeuwen. Optimization and approximation on systems of geometric objects. PhD Thesis, University of Amsterdam, 2009, http://dare.uva.nl/record/307611.

[23]

E. J. van Leeuwen and J. van Leeuwen. Convex polygon intersection graphs. In U. Brandes and S. Cornelsen, editors, Graph Drawing 2010, Proceedings, Lecture Notes in Computer Science, volume 6205, pages 377--388. Springer-Verlag, Berlin, 2011.

Digital Library

Cited By

Brimkov VKafer SSzczepankiewicz MTerhaar J(2014)On Intersection Graphs of Convex PolygonsProceedings of the 16th International Workshop on Combinatorial Image Analysis - Volume 846610.1007/978-3-319-07148-0_4(25-36)Online publication date: 28-May-2014
https://dl.acm.org/doi/10.1007/978-3-319-07148-0_4
Mcdiarmid CMüLler T(2013)Integer realizations of disk and segment graphsJournal of Combinatorial Theory Series B10.1016/j.jctb.2012.09.004103:1(114-143)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.jctb.2012.09.004
Junosza-Szaniawski KKratochvíl JPergel MRzążewski P(2012)Beyond Homothetic Polygons: Recognition and Maximum CliqueAlgorithms and Computation10.1007/978-3-642-35261-4_64(619-628)Online publication date: 2012
https://doi.org/10.1007/978-3-642-35261-4_64

Index Terms

Integer representations of convex polygon intersection graphs

Recommendations

Integer Representations of Convex Polygon Intersection Graphs

We determine tight bounds on the smallest-size integer grid needed to represent the $n$-node intersection graphs of a convex polygon $P$ with P given in rational coordinates. The intersection graphs use only polygons that are geometrically similar to $P$ (...
Decomposing a simple polygon into pseudo-triangles and convex polygons

In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-...
Coloring Intersection Graphs of Arc-Connected Sets in the Plane

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line $$L$$L if the intersection of any member with $$L$$L is a nonempty segment. It is proved that the intersection graphs of simple ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

June 2011

532 pages

ISBN:9781450306829

DOI:10.1145/1998196

Program Chairs:
Ferran Hurtado
Universitat Politècnica de Catalunya
,
Marc van Kreveld
Utrecht University

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '11

Sponsor:

SoCG '11: Symposium on Computational Geometry

June 13 - 15, 2011

Paris, France

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
89
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brimkov VKafer SSzczepankiewicz MTerhaar J(2014)On Intersection Graphs of Convex PolygonsProceedings of the 16th International Workshop on Combinatorial Image Analysis - Volume 846610.1007/978-3-319-07148-0_4(25-36)Online publication date: 28-May-2014
https://dl.acm.org/doi/10.1007/978-3-319-07148-0_4
Mcdiarmid CMüLler T(2013)Integer realizations of disk and segment graphsJournal of Combinatorial Theory Series B10.1016/j.jctb.2012.09.004103:1(114-143)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.jctb.2012.09.004
Junosza-Szaniawski KKratochvíl JPergel MRzążewski P(2012)Beyond Homothetic Polygons: Recognition and Maximum CliqueAlgorithms and Computation10.1007/978-3-642-35261-4_64(619-628)Online publication date: 2012
https://doi.org/10.1007/978-3-642-35261-4_64

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents