Sphere and dot product representations of graphs

DOI10.1007/s00454-012-9394-8zbMath1238.05180MaRDI QIDQ411410

Ross J. Kang, Tobias Müller

Publication date: 4 April 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9394-8

zbMATH Keywords

sphericity; dot product dimension; geometric representations of graphs

Mathematics Subject Classification ID

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Conflict-Free Coloring of Intersection Graphs, Unnamed Item, Unnamed Item, What Graphs are 2-Dot Product Graphs?, On Embeddability of Unit Disk Graphs onto Straight Lines, Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs, The Complexity of Drawing a Graph in a Polygonal Region, Global Rigidity of Unit Ball Graphs, Computing a maximum clique in geometric superclasses of disk graphs, Balanced line separators of unit disk graphs, On the Complexity of Some Geometric Problems With Fixed Parameters, Unnamed Item, Intersection graphs of non-crossing paths, On embeddability of unit disk graphs onto straight lines, Establishing herd immunity is hard even in simple geometric networks, The Complexity of Drawing Graphs on Few Lines and Few Planes, Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality, Logical labeling schemes, What graphs are 2-dot product graphs?, Fixed points, Nash equilibria, and the existential theory of the reals, On complexity of multidistance graph recognition in \(\mathbb{R}^1\), Implicit representation conjecture for semi-algebraic graphs, On arrangements of orthogonal circles, Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit, \( L ( 2 , 1 )\)-labeling of disk intersection graphs, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space graphs and sphericity
• Realizability of combinatorial types of convex polyhedra over fields
• On embedding of graphs into Euclidean spaces of small dimension
• Dot product representations of graphs
• Unit disk graph recognition is NP-hard
• Efficient graph representations
• Embeddings of graphs in Euclidean spaces
• Geometrical embeddings of graphs
• Threshold graphs and related topics
• Integer realizations of disk and segment graphs
• Optimal greedy algorithms for indifference graphs
• The Number of Bits Needed to Represent a Unit Disk Graph
• Implicat Representation of Graphs
• On the combinatorial and algebraic complexity of quantifier elimination
• Oriented Matroids
• Algorithms in real algebraic geometry