<link rel="stylesheet" href="styles.cf390c6bfbe7555f.css">

Browsing by Author "Wu, KP"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item type:Item,
    Disproving a conjecture on planar visibility graphs
    (2001-03-28)
    Chen, CY
    ;
    Wu, KP
    ;
    應用數學系
    ;
    Department of Applied Mathematics
    Two vertices A and B of a simple polygon P are (mutually) visible if AB does not intersect the exterior of P. A graph G is a visibility graph if there exists a simple polygon P such that each vertex of G corresponds to a vertex of P and two vertices of G are joined by an edge if and only if their corresponding vertices in P are visible, No characterization of visibility graphs is available. Abello, Lin and Pisupati conjectured that every hamiltonian maximal planar graph with a 3-clique ordering is a visibility graph. In this paper, we disprove this conjecture. (C) 2001 Elsevier Science B.V. All rights reserved.