Results 81 to 90 of about 1,769 (162)
On an interpolation property of outerplanar graphs
Discrete Applied Mathematics, 2006 Let \(D\) be an acyclic orientation of a graph \(G\). An arc of \(D\) is dependent if a directed cycle is created when it is reversed. Denote by \(d(D)\) the number of dependent arcs in \(D\). Let \(d_{\min}(G)\) be the minimum \(d(D)\), and \(d_{\max}(G)\) the maximum \(d(D)\), over all acyclic orientations \(D\) of \(G\).
Ko-Wei Lih, Chen-Ying Lin, Li-Da Tong
openaire +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
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
Generating Outerplanar Graphs Uniformly at Random [PDF]
, 2006 This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively.We show how to generate labelled and unlabelled outerplanar graphs ...
Kang, Mihyun, Bodirsky, Manuel
core +1 more source
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
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
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 refinement operator for outerplanar graphs
, 2022 S.95-97Outerplanar graphs form a practically relevant class of graphs which appear efficiently computable bottom-up refinement operator for tenuous outerplanar graphs defined by combining techniques from first-order learning, algebraic graph theory, and ...
Horvath, Tamas +2 more
core +1 more source
Every Property of Outerplanar Graphs is Testable [PDF]
, 2016 A D-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most D from v. We show that the structure of an outerplanar graph on n vertices is determined, up to modification (insertion or deletion) of at most ...
Newman, Ilan +2 more
core +1 more source
External Memory Algorithms for Outerplanar Graphs
, 1999 We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a2-separator of size 2 for a given outerplanar graph.
Norbert Zeh +3 more
core +1 more source