2016年
Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
GRAPH DRAWING AND NETWORK VISUALIZATION (GD 2016)
- ,
- 巻
- 9801
- 号
- 開始ページ
- 321
- 終了ページ
- 334
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-319-50106-2_25
- 出版者・発行元
- SPRINGER INTERNATIONAL PUBLISHING AG
Thomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335-341, 1988].
In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Reembedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration.
In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Reembedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration.
- リンク情報
-
- DOI
- https://doi.org/10.1007/978-3-319-50106-2_25
- DBLP
- https://dblp.uni-trier.de/rec/conf/gd/HongN16
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000405478500025&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/conf/gd/gd2016.html#conf/gd/HongN16
- ID情報
-
- DOI : 10.1007/978-3-319-50106-2_25
- ISSN : 0302-9743
- eISSN : 1611-3349
- DBLP ID : conf/gd/HongN16
- Web of Science ID : WOS:000405478500025