Results 91 to 100 of about 2,073 (195)
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
Journal of Graph Algorithms and Applications, 2003 This paper investigates the following question: Given a grid ϕ, where ϕ is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at (integral) grid points of ϕ?
Stefan Felsner +2 more
doaj +1 more source
Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs [PDF]
Maximal outerplanar graphs are characterized using three different classes of graphs. A path-neighborhood graph is a connected graph in which every neighborhood induces a path. The triangle graph $T(G)$ has the triangles of the graph $G$ as its vertices,
Novick, B., Laskar, R.C., Mulder, H.M.
core
Excluded-Minor Characterization of Apex-Outerplanar Graphs [PDF]
, 2016 The class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: (Formula presented.) and (Formula presented.). The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed.
Ding, Guoli, Dziobiak, Stan
core +1 more source
Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
Journal of Graph Algorithms and Applications, 2006 Let G=(V,E) be a graph with n vertices and let P be a set of n points in the plane. We show that deciding whether there is a planar straight-line embedding of G such that the vertices V are embedded onto the points P is NP-complete, even when G is 2 ...
Sergio Cabello
doaj +1 more source
A fast parallel algorithm for optimal edge-colouring of outerplanar graphs [PDF]
We prove that every outerplanar graph can be optimally edge-coloured in polylog time using a polynomial number of processors on a parallel random access machine without write conflicts (P-RAM)
Gibbons, Alan (Alan M.) +1 more
core
Edge covering pseudo-outerplanar graphs with forests [PDF]
, 2011 A graph is pseudo-outerplanar if each block has an embedding on the plane in such a way that the vertices lie on a fixed circle and the edges lie inside the disk of this circle with each of them crossing at most one another.
Zhang, Xin, Liu, Guizhen, Wu, Jian-Liang
core
Algorithm-based radio labeling for optimal channel assignment in outerplanar graphs
Frontiers in Computer ScienceIntroductionRadio labeling of graphs extends the channel assignment problem by assigning non-negative integers to vertices of a connected graph G such that |h(℘)−h(𝓆)|≥diam(ℊ)+1−d(℘, 𝓆).
Baskar Mari, Ravi Sankar Jeyaraj
doaj +1 more source
Extremal eigenvalues of outerplanar graphs [PDF]
The extremal eigenvalues including maximum eigenvalues and the minimum eigenvalues about outerplanar graphs are investigated in this paper. Some structural characterizations about the (edge) maximal bipartite outerplanar graphs are represented.
Yu, Guanglong
core +1 more source
k-colored Point-set Embeddability of Outerplanar Graphs
Journal of Graph Algorithms and Applications, 2008 This paper addresses the problem of designing drawing algorithms that receive as input a planar graph G, a partitioning of the vertices of G into k different semantic categories V0,…, Vk−1, and k disjoint sets S0, …, Sk−1 of points in the plane with |Vi|=
Emilio Di Giacomo +5 more
doaj +1 more source
Computing Obstruction Sets for Almost Outerplanar Graphs
, 2015 Full text is available to authenticated members of The University of Auckland only.Focusing on the Outerplanar graph family, we present relevant methodologies and known techniques for computing finite obstruction sets under a well-quasi-ordering.
Elliott, David
core