Accession Number:

ADA048051

Title:

On the Planarity of Hypergraphs.

Descriptive Note:

Technical note,

Corporate Author:

STANFORD UNIV CALIF DIGITAL SYSTEMS LAB

Personal Author(s):

• VANCleemput,W. M.

Report Date:

1977-06-01

Pagination or Media Count:

9.0

Abstract:

Two definitions for the planarity of a hypergraph will be given. These definitions are related to the problem of modelling circuits for circuit layout. It is shown that if a hypergraph is planar according to the first definition, then it is planar according to the second definition, but the reverse does not hold. Testing the planarity can be done in linear time by using the first definition but requires an enumeration using the second definition. The more accurate model for the circuit layout problem uses the second definition. Author

Descriptors:

• *MATHEMATICAL MODELS
• *GRAPHS
• *CIRCUIT ANALYSIS
• PLANAR STRUCTURES
• MAPPING(TRANSFORMATIONS)

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE