Nothing Special   »   [go: up one dir, main page]

Hopcroft et al., 1974 - Google Patents

Efficient planarity testing

Hopcroft et al., 1974

View PDF
Document ID
1646921410828739524
Author
Hopcroft J
Tarjan R
Publication year
Publication venue
Journal of the ACM (JACM)

External Links

Snippet

This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The …
Continue reading at dl.acm.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30958—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G06F17/5068—Physical circuit design, e.g. layout for integrated circuits or printed circuit boards
    • G06F17/5077—Routing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G06F17/5009—Computer-aided design using simulation
    • G06F17/5022—Logic simulation, e.g. for logic circuit operation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/36—Preventing errors by testing or debugging software
    • G06F11/3604—Software analysis for verifying properties of programs
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled

Similar Documents

Publication Publication Date Title
Hopcroft et al. Efficient planarity testing
Chiang et al. External-memory graph algorithms
Tarjan Depth-first search and linear graph algorithms
McHugh Algorithmic graph theory
Mateti et al. On algorithms for enumerating all circuits of a graph
US5497334A (en) Application generator for use in verifying a hierarchical circuit design
US5481473A (en) System and method for building interconnections in a hierarchical circuit design
Tarjan Sorting using networks of queues and stacks
Hecht et al. A simple algorithm for global data flow analysis problems
US5519628A (en) System and method for formulating subsets of a hierarchical circuit design
US5528508A (en) System and method for verifying a hierarchical circuit design
Arge The I/O-complexity of ordered binary-decision diagram manipulation
Mareš The saga of minimum spanning trees
Rauzy et al. Assessment of large automatically generated fault trees by means of binary decision diagrams
Klas et al. TOMSPIN-a tool for modeling with stochastic Petri nets
Ricciardi Lectures in applied mathematics and informatics
McBryan et al. The multigrid method on parallel processors
Geffert Bridging across the log (n) space frontier
KR20010024944A (en) A method for manufacturing and designing an electronic device and electronic apparatus
Livadas et al. Slicing in the presence of pointer variables
Toledo Extremal polygon containment problems and other issues in parametric searching
Fernández-Baca et al. Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
Lee et al. Closed partition lattice and machine decomposition
Vijayan Design Implementation and Theory of a VLSI Layout Language
Gazit et al. A randomized parallel algorithm for planar graph isomorphism