Plane Representations of Graphs and Visibility between Parallel Segments.

Abstract

Several layout compaction strategies for VLSI are based on the concept of visibility between parallel segments, where we say that two parallel segments of a given set are visible if they can be joined by a segment orthogonal to them, which does not intersect any other segment. This paper studies visibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments drawn between visible vertex-segments. Clearly, every graph that admits such a representation must be a planar. The authors consider three types of visibility representations, and give complete characterizations of the classes of graphs that admit them. Furthermore, they present linear time algorithms for testing the existence of and constructing visibility representations of planar graphs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1985
Accession Number
ADA161689

Entities

People

  • Ioannis G. Tollis
  • Roberto Tamassia

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Boundaries
  • Classification
  • Computational Science
  • Computations
  • Computer Science
  • Construction
  • Critical Path Methods
  • Embedding
  • Engineering
  • Illinois
  • Intervals
  • Mathematics
  • Security
  • Visibility

Readers

  • Climatology
  • Graph Algorithms and Convex Optimization.