English  |  正體中文  |  简体中文  |  Items with full text/Total items : 26988/38789
Visitors : 2347932      Online Users : 28
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/51718

Title: IMPROVED COMPACT VISIBILITY REPRESENTATION OF PLANAR GRAPH VIA SCHNYDER’S REALIZER
Authors: Ching-Chi Lin
Hsueh-I Lu
I-Fan Sun
Contributors: 國立臺灣海洋大學:資訊工程學系
Keywords: visibility representation
planar graph algorithm
graph drawing
realizer
canonical ordering
Date: 2004-07
Issue Date: 2018-12-21T02:55:19Z
Publisher: SIAM Journal on Discrete Math
Abstract: Abstract: Let G be an n-node planar graph. In a visibility representation of G, each node of G
is represented by a horizontal line segment such that the line segments representing any two adjacent
nodes of G are vertically visible to each other. In the present paper we give the best known compact
visibility representation of G. Given a canonical ordering of the triangulated G, our algorithm draws
the graph incrementally in a greedy manner. We show that one of three canonical orderings obtained
from Schnyder’s realizer for the triangulated G yields a visibility representation of G no wider than
 22n−40
15
. Our easy-to-implement O(n)-time algorithm bypasses the complicated subroutines for
four-connected components and four-block trees required by the best previously known algorithm of
Kant. Our result provides a negative answer to Kant’s open question about whether  3n−6
2
is a
worst-case lower bound on the required width. Also, if G has no degree-three (respectively, degreefive) internal node, then our visibility representation for G is no wider than  4n−9
3
(respectively,
 4n−7
3

). Moreover, if G is four-connected, then our visibility representation for G is no wider than
n − 1, matching the best known result of Kant and He. As a by-product, we give a much simpler
proof for a corollary of Wagner’s theorem on realizers due to Bonichon, Le Sa¨ec, and Mosbah.
Relation: 18(1) pp.19-29
URI: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/51718
Appears in Collections:[資訊工程學系] 期刊論文

Files in This Item:

File Description SizeFormat
index.html0KbHTML7View/Open


All items in NTOUR are protected by copyright, with all rights reserved.

 


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback