No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs

• RAHMAN Md. Saidur

  Graduate School of Information Sciences, Tohoku University

• EGI Noritsugu

  Graduate School of Information Sciences, Tohoku University

• NISHIZEKI Takao

  Graduate School of Information Sciences, Tohoku University

抄録

A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdivisions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.

収録刊行物

• IEICE transactions on information and systems

  IEICE transactions on information and systems 88 (1), 23-30, 2005-01-01

  一般社団法人電子情報通信学会

キーワード

• planar graph
• algorithm
• graph drawing
• orthogonal drawing
• bend

詳細情報

• CRID: 1571698602418953728
• NII論文ID: 110003214131
• NII書誌ID: AA10826272
• ISSN: 09168532
• 本文言語コード: en
• データソース種別:
  • CiNii Articles