More Web Proxy on the site http://driver.im/

research-article

The point-set embeddability problem for plane graphs

Authors:

Martin VatshelleAuthors Info & Claims

SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

Pages 41 - 50

https://doi.org/10.1145/2261250.2261257

Published: 17 June 2012 Publication History

Abstract

In this paper, we study the point-set-embeddability-problem, i.e., given a planar graph and a set of points, is there a mapping of the vertices to the points such that the resulting straight-line drawing is planar? It was known that this problem is NP-hard if the embedding can be chosen, but becomes polynomial for triangulated graphs of treewidth 3. We show here that in fact it can be answered for all planar graphs with a fixed combinatorial embedding that have constant treewidth and constant face-degree.

We also prove that as soon as one of the conditions is dropped (i.e., either the treewidth is unbounded or some faces have large degrees), point-set-embeddability with a fixed embedding becomes NP-hard. The NP-hardness holds even for a 3-connected planar graph with constant treewidth, triangulated planar graphs, or 2-connected outer-planar graphs.

References

[1]

S. Arnborg, D.G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277--284, 1987.

Digital Library

[2]

M. Badent, E. Di Giacomo, and G. Liotta. Drawing colored graphs on colored points. Theor. Comput. Sci., 408(2--3):129--142, 2008.

Digital Library

[3]

H. Bodlaender. Treewidth: algorithmic techniques and results. In Mathematical Foundations of Computer Science (MFCS 1997). volume 1295 of Lecture Notes in Computer Science, pages 19--36. Springer-Verlag, 1997.

Digital Library

[4]

H. L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358--402, 1996.

Digital Library

[5]

P. Bose. On embedding an outer-planar graph in a point set. Computational Geometry: Theory and Applications. 23(3):303--312, 2002.

Digital Library

[6]

V. Bouchitte, F. Mazoit, and I. Todinca. Chordal embeddings of planar graphs. Discrete Mathematics, 273(1--3):85--102, 2003.

[7]

S. Cabello. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Journal of Graph Algorithms and Applications, 10(2):353--363. 2006.

[8]

N. Castaneda and J. Urrutia. Straight line embeddings of planar graphs on point sets. In Canadian Conference on Computational Geometry (CCCG '96). pages 312--318, 1996.

Digital Library

[9]

S. Durocher and D. Mondal. On the hardness of point-set embeddability. In 6th Workshop on Algorithms and Computation (WALCOM 2012). volume 7157 of Lecture Notes in Computer Science, pages 148--159. Springer, 2012.

Digital Library

[10]

I. Fary. On straight line representation of planar graphs. Acta Scientiarum Mathematicarum (Szeged), 11:229--233, 1948.

[11]

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

[12]

M.R. Gary and D.S. Johnson. Computers and Intracatablity: A Guide to the Theory on NP-completeness. Freeman, 1979.

Digital Library

[13]

M. Geyer, M. Kaufmann, T. Mchedlidze, and A. Symvonis. Upward point-set embeddability. In Theory and Practice of Computer Science (SOFSEM 2011). volume 6543 of Lecture Notes in Computer Science, pages 272--283. Springer, 2011.

Digital Library

[14]

E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer, and S. Wismath. Constrained point-set embeddability of planar graphs. Intl. Journal of Computational Geometry and Applications. 20(5):577--600, 2010.

[15]

P. Gritzmann, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specified positions. American Mathematic Monthly, 98:165--166, 1991.

[16]

T.M. Moosa and M. Sohel Rahman. Improved algorithms for the point-set embeddability problem for plans 3-trees. In COCOON, volume 6842 of Lecture Notes in Computer Science, pages 204--212. Springer, 2011.

Digital Library

[17]

N. Nestoridis and D. Thilikos. Square roots of minor closed graph classes, 2011. Presented at EuroComb'11.

[18]

R.I. Nishat, D. Mondal, and Md. S. Rahman. Point-set embeddings of plane 3-trees. Comput. Geom.}, 45(3):88--98, 2012.

Digital Library

[19]

N. Robertson and P. Seymour. Graph minors. {XVIII}. Tree-decompositions and well-quasi-ordering. J. Combin. Theory Ser. B, 89(1):77--108, 2003.

Digital Library

[20]

N. Robertson and P.D. Seymour. Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B, 52(2):153--190, 1991.

Digital Library

[21]

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

Digital Library

[22]

P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217--241, 1994.

[23]

M. Sharir and E. Welzl. On the number of crossing-free matchings, (cycles, and partitions). In Symposium on Discrete Algorithms (SODA 2006), pages 860--869. ACM Press, 2006.

Digital Library

[24]

S. Stein. Convex maps. In American Mathematical Society, volume 2, pages 464--466. 1951.

[25]

D. M. Thilikos, M. Serna, and H. L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. Journal of Algorithms, 56:1--24, 2005.

Digital Library

[26]

D. M. Thilikos, M. Serna, and H. L. Bodlaender. Cutwidth II: Algorithms for partial ω-trees of bounded degree. Journal of Algorithms, 56:25--49, 2005.

Digital Library

[27]

K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung. 46:26--32, 1936.

Cited By

Lodha NOrdyniak SSzeider S(2019)A SAT Approach to BranchwidthACM Transactions on Computational Logic10.1145/332615920:3(1-24)Online publication date: 31-May-2019
https://dl.acm.org/doi/10.1145/3326159
Yamazaki K(2018)Inapproximability of Rank, Clique, Boolean, and Maximum Induced Matching-Widths under Small Set Expansion HypothesisAlgorithms10.3390/a1111017311:11(173)Online publication date: 31-Oct-2018
https://doi.org/10.3390/a11110173
Hosseinzadegan MBagheri A(2016)Optimal point-set embedding of wheel graphs and a sub-class of 3-treesJapan Journal of Industrial and Applied Mathematics10.1007/s13160-016-0232-x33:3(621-628)Online publication date: 25-Nov-2016
https://doi.org/10.1007/s13160-016-0232-x
Show More Cited By

Index Terms

The point-set embeddability problem for plane graphs
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Drawing colored graphs on colored points

Let G be a planar graph with n vertices and with a partition of the vertex set into subsets V"0,...,V"k"-"1 for some positive integer 1@?k@?n. Let S be a set of n distinct points in the plane with a partition into subsets S"0,...,S"k"-"1 with |V"i|=|S"i|...
Point-set embeddings of plane 3-trees

A straight-line drawing of a plane graph G is a planar drawing of G, where each vertex is drawn as a point and each edge is drawn as a straight line segment. Given a set S of n points in the Euclidean plane, a point-set embedding of a plane graph G with ...
Point-set embeddings of plane 3-trees
GD'10: Proceedings of the 18th international conference on Graph drawing

A straight-line drawing of a plane graph G is a planar drawing of G, where each vertex is drawn as a point and each edge is drawn as a straight-line segment. Given a set S of n points on the Euclidean plane, a point-set embedding of a plane graph G with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

June 2012

436 pages

ISBN:9781450312998

DOI:10.1145/2261250

Program Chairs:
Tamal Dey
The Ohio State University, USA
,
Sue Whitesides
University of Victoria, Canada

Copyright © 2012 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: 17 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '12

Sponsor:

SoCG '12: Symposium on Computational Geometry 2012

June 17 - 20, 2012

North Carolina, Chapel Hill, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
152
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lodha NOrdyniak SSzeider S(2019)A SAT Approach to BranchwidthACM Transactions on Computational Logic10.1145/332615920:3(1-24)Online publication date: 31-May-2019
https://dl.acm.org/doi/10.1145/3326159
Yamazaki K(2018)Inapproximability of Rank, Clique, Boolean, and Maximum Induced Matching-Widths under Small Set Expansion HypothesisAlgorithms10.3390/a1111017311:11(173)Online publication date: 31-Oct-2018
https://doi.org/10.3390/a11110173
Hosseinzadegan MBagheri A(2016)Optimal point-set embedding of wheel graphs and a sub-class of 3-treesJapan Journal of Industrial and Applied Mathematics10.1007/s13160-016-0232-x33:3(621-628)Online publication date: 25-Nov-2016
https://doi.org/10.1007/s13160-016-0232-x
Aichholzer OHackl TLutteropp SMchedlidze TVogtenhuber B(2014)Embedding Four-Directional Paths on Convex Point SetsRevised Selected Papers of the 22nd International Symposium on Graph Drawing - Volume 887110.1007/978-3-662-45803-7_30(355-366)Online publication date: 24-Sep-2014
https://dl.acm.org/doi/10.1007/978-3-662-45803-7_30
Fulek RTóth C(2013)Universal point sets for planar three-treesProceedings of the 13th international conference on Algorithms and Data Structures10.1007/978-3-642-40104-6_30(341-352)Online publication date: 12-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40104-6_30
Durocher SMondal D(2013)Plane 3-treesProceedings of the 13th international conference on Algorithms and Data Structures10.1007/978-3-642-40104-6_26(291-303)Online publication date: 12-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40104-6_26
Frati FGlisse MLenhart WLiotta GMchedlidze TNishat R(2012)Point-Set embeddability of 2-colored treesProceedings of the 20th international conference on Graph Drawing10.1007/978-3-642-36763-2_26(291-302)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-36763-2_26
Rahmati ZWhitesides SKing V(2012)Kinetic and stationary point-set embeddability for plane graphsProceedings of the 20th international conference on Graph Drawing10.1007/978-3-642-36763-2_25(279-290)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-36763-2_25

View Options

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