Representations of graphs and networks (coding, layouts and embeddings)
From MaRDI portal
Publication:1174904
DOI10.1007/BF01097528zbMath0784.05054OpenAlexW2000271677MaRDI QIDQ1174904
S. V. Yushmanov, V. P. Kozyrev
Publication date: 25 June 1992
Published in: Journal of Soviet Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01097528
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Cites Work
- Reconstructing the shape of a tree from observed dissimilarity data
- On the contact dimensions of graphs
- On the genus and thickness of graphs
- Computing the boxicity of a graph by covering its complement by cointerval graphs
- Large processors are good in VLSI chips
- Space graphs and sphericity
- Recognizing graphs with fixed interval number is NP-complete
- Applications of edge coverings by cliques
- On rigid circuit graphs
- The interval number of a planar graph: Three intervals suffice
- Isometric embedding in products of complete graphs
- A problem of Berge
- Some results about the interval number of a graph
- A new proof of a theorem of Graham and Pollak
- On the sphericity and cubicity of graphs
- Crossing-critical edges and Kuratowski subgraphs of a graph
- The edge intersection graphs of paths in a tree
- Dominating sets for split and bipartite graphs
- Chronological orderings of interval graphs
- A framework for solving VLSI graph layout problems
- Drawing plane graphs nicely
- Tolerance graphs
- A generalization of outerplanar graphs
- A characterization of circle graphs
- Finding Hamiltonian circuits in proper interval graphs
- Representing a planar graph by vertical lines joining different levels
- Determining the interval number of a triangle-free graph
- Uniquely and faithfully embeddable projective-planar triangulations
- Proof of the squashed cube conjecture
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- On the complexity of partitioning graphs into connected subgraphs
- Reconnaissance des graphes de cordes
- Edge and vertex intersection of paths in a tree
- Triangulated edge intersection graphs of paths in a tree
- Decomposition by clique separators
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Split graphs of Dilworth number 2
- A note on the interval number of a graph
- Irrepresentability by multiple intersection, or why the interval number is unbounded
- On cubic graphs which are irreducible for nonorientable surfaces
- Dominating sets and domatic number of circular arc graphs
- Homogeneously representable interval graphs
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- On the addressing problem for directed graphs
- Simplicial decompositions of graphs - some uniqueness results
- Decomposition of graphs and monotone formula size of homogeneous functions
- On the Euler genus of a 2-connected graph
- On the non-orientable genus of a 2-connected graph
- Embeddings of infinite graphs
- Minimum dimension embedding of finite metric spaces
- Interval representations of planar graphs
- Sphericity exceeds cubicity for almost all complete bipartite graphs
- Intersection graphs of paths in a tree
- Characterizing intersection classes of graphs
- The toroidal splitting number of the complete graph \(K_ n\)
- Graph minors. VI. Disjoint paths across a disc
- Distance-hereditary graphs
- On an extremal problem concerning the interval number of a graph
- A unified approach to visibility representations of planar graphs
- Rectilinear planar layouts and bipolar orientations of planar graphs
- Finding small simple cycle separators for 2-connected planar graphs
- Re-embedding of projective-planar graphs
- Fundamentals of planar ordered sets
- Enumeration of projective-planar embeddings of graphs
- A characterization of the minimalbasis of the torus
- An infinite set of torus triangulations of connectivity 5 whose graphs are not uniquely embeddable in the torus
- An additivity theorem for the genus of a graph
- Irredundancy in multiple interval representations
- Nonorientable genus of nearly complete bipartite graphs
- The splitting number of the complete graph in the projective plane
- Symmetries of knotted hypothetical molecular graphs
- Some applications of graph theory to the study of polymer configuration
- Combinatorial characterization of hexagonal systems
- Dwarf, brick, and triangulation of the torus
- A tight lower bound on the size of visibility graphs
- A note on visibility graphs
- Embedding of trees in Euclidean spaces
- On the Euclidean dimension of a wheel
- The asymptotic number of tree-rooted maps on a surface
- Covering graphs by the minimum number of equivalence relations
- Poset boxicity of graphs
- Man-machine theorem proving in graph theory
- Tree-decompositions, tree-representability and chordal graphs
- Intersection graphs of halflines and halfplanes
- Matching extension and the genus of a graph
- A polynomial characterization of some graph partitioning problems
- The spherical genus and virtually planar graphs
- On the Euclidean dimension of a complete multipartite graph
- Min Cut is NP-complete for edge weighted trees
- Embedding rectilinear graphs in linear time
- Graph minors. VII: Disjoint paths on a surface
- Strict 2-threshold graphs
- Reducing prime graphs and recognizing circle graphs
- Algorithmic aspects of intersection graphs and representation hypergraphs
- End vertices in interval graphs
- Rubber bands, convex embeddings and graph connectivity
- The Johnson-Lindenstrauss lemma and the sphericity of some graphs
- Algorithms for plane representations of acyclic digraphs
- Clique partitions and clique coverings
- A characterization of Robert's inequality for boxicity
- A note on circular dimension
- Planarity and duality of finite and infinite graphs
- On intersections of interval graphs
- Extremal values of the interval number of a graph. II
- On time graphs
- Complexity of representation of graphs by set systems
- An application of vertex packing to data analysis in the evaluation of pavement deterioration
- On the number of graphs without 4-cycles
- The splittance of a graph
- Comparability graphs and intersection graphs
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- Intersection graphs of curves in the plane
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Free trees and bidirectional trees as representations of psychological distance
- The circular dimension of a graph
- A construction of thickness-minimal graphs
- The splitting number of the complete graph
- Uniqueness and faithfulness of embedding of toroidal graphs
- An asymptotically optimal layout for the shuffle-exchange graph
- A note on the metric properties of trees
- A characterisation of rigid circuit graphs
- Representation of a tree with p hanging vertices by 2p-3 elements of its distance matrix
- Incidence matrices and interval graphs
- Intersection representations of graphs by arcs
- Matrix characterizations of circular-arc graphs
- Distance-preserving subgraphs of hypercubes
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Structure theorems for some circular-arc graphs
- On the Optimal Layout of Planar Graphs with Fixed Boundary
- On a Modified Concept of Thickness of a Graph
- On double and multiple interval graphs
- Isometric embeddings of graphs
- Convex Representations of Graphs
- Representation of a finite graph by a set of intervals on the real line
- OptimalI-Intersection assignments for graphs: A linear programming approach
- Automorphism properties of embedded graphs
- Crossing Number is NP-Complete
- Edges and Kuratowski Subgraphs of Non-Planar Graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Digital metrics: A graph-theoretical approach
- On minimal-node-cost planar embeddings
- The cycle space of an embedded graph
- A digraph represented by a family of boxes or spheres
- Solving Undirected Graph Problems on VLSI
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- On Comparability and Permutation Graphs
- On Isometric Embeddings of Graphs
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Steiner trees, connected domination and strongly chordal graphs
- The frame dimension and the complete overlap dimension of a graph
- Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
- The optimal representation of disjoint iso-oriented rectangles in two-dimensional trees
- Planar 3DM is NP-complete
- Single bend wiring
- The NP-completeness column: an ongoing guide
- Three-Dimensional Circuit Layouts
- The Editor's Corner: Finite Lists of Obstructions
- Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées
- Relative Embeddings of Graphs on Closed Surfaces
- On the Complexity of Covering Vertices by Faces in a Planar Graph
- Stability in circular arc graphs
- The maximum interval number of graphs with given genus
- On the Interval Number of a Triangulated Graph
- Enumerating 2-Cell Imbeddings of Connected Graphs
- The structure of distances in networks
- An improved edge bound on the interval number of a graph
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- The computational complexity of graph problems with succinct multigraph representation
- A characterization of ptolemaic graphs
- Representations of chordal graphs as subtrees of a tree
- An Efficient Test for Circular-Arc Graphs
- Nonorientable genus of cartesian products of regular graphs
- Tree structures for proximity data
- Dominating Sets in Chordal Graphs
- On the toroidal thickness of graphs
- New lower bound techniques for VLSI
- Efficient algorithms for interval graphs and circular-arc graphs
- Orientations of circle graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- A Depth-First-Search Characterization of Planarity
- Decomposition of Directed Graphs
- Extremal Values of the Interval Number of a Graph
- The Complexity of Coloring Circular Arcs and Chords
- Covering edges by cliques with regard to keyword conflicts and intersection graphs
- Crossing Theory and Hierarchy Mapping
- Circular permutation graphs
- An Optimal Diagonal Tree Code
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
- A note on the tree realizability of a distance matrix
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- On the Addressing Problem for Loop Switching
- Permutation Graphs and Transitive Graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- A Characterization of Comparability Graphs and of Interval Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
