Moving vertices to make drawings plane
| العنوان: | Moving vertices to make drawings plane |
|---|---|
| المؤلفون: | Goaoc, X., Kratochvil, J., Okamoto, Y., Shin, C.S., Wolff, A., Hong, S.K., Nishizeki, T., Quan, W. |
| المساهمون: | Effective Geometric Algorithms for Surfaces and Visibility (VEGAS), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Discrete Optimization Laboratory, Toyohashi University of Technology, Departement of Electronics and Information Engineering, Hankuk University of Foreign Studies, Faculteit Wiskunde & Informatica, Technische Universiteit Eindhoven (TU/e), Algorithms |
| المصدر: | 15th International Symposium on Graph Drawing 15th International Symposium on Graph Drawing, Sep 2007, Sydney, Australia. pp.101-112, ⟨10.1007/978-3-540-77537-9_13⟩ ResearcherID Graph Drawing (15th International Symposium, GD'07, Sydney, Australia, September 23-26, 2007, Revised Papers), 101-112 STARTPAGE=101;ENDPAGE=112;TITLE=Graph Drawing (15th International Symposium, GD'07, Sydney, Australia, September 23-26, 2007, Revised Papers) Graph Drawing ISBN: 9783540775362 Graph Drawing |
| سنة النشر: | 2008 |
| مصطلحات موضوعية: | Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Planar straight-line graph, Slope number, 0102 computer and information sciences, Computational Complexity (cs.CC), [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Combinatorics, symbols.namesake, Graph drawing, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Outerplanar graph, Wheel graph, Dominance drawing, 0101 mathematics, Mathematics, Discrete mathematics, Book embedding, 010102 general mathematics, Planar graph, Computer Science - Computational Complexity, 010201 computation theory & mathematics, symbols, Computer Science - Computational Geometry, Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS |
| الوصف: | A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by moving some of the vertices. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to turn $\delta$ into a plane drawing of $G$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate, and we give explicit bounds on shift$(G,\delta)$ when $G$ is a tree or a general planar graph. Our hardness results extend to 1BendPointSetEmbeddability, a well-known graph-drawing problem. Comment: This paper has been merged with http://arxiv.org/abs/0709.0170 |
| اللغة: | English |
| ردمك: | 978-3-540-77536-2 |
| تدمد: | 0302-9743 |
| DOI: | 10.1007/978-3-540-77537-9_13 |
| DOI: | 10.1007/978-3-540-77537-9_13⟩ |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::941e151e661442f28fd8a6d8c0dae33f https://doi.org/10.1007/978-3-540-77537-9_13 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....941e151e661442f28fd8a6d8c0dae33f |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783540775362 |
|---|---|
| تدمد: | 03029743 |
| DOI: | 10.1007/978-3-540-77537-9_13 |