Orthogonal drawings and crossing numbers of the Kronecker product of two cycles

DOI10.1016/j.jpdc.2011.11.009zbMath1242.68193OpenAlexW2094825239MaRDI QIDQ433407

Pranava K. Jha, Savitri Devisetty

Publication date: 13 July 2012

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jpdc.2011.11.009

zbMATH Keywords

cyclesgridsgraph minorKronecker productgraph algorithmscrossing numberCartesian productvertex partitionorthogonal drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (3)

Rotation and crossing numbers for join products ⋮ Cycle Kronecker products that are representable as optimal circulants ⋮ On the crossing number for Kronecker product of a tripartite graph with path

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• The crossing numbers of join of the special graph on six vertices with path and cycle
• Perfect \(r\)-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh
• The crossing number of \(C_3\times C_n\)
• Embeddings of star graphs into optical meshes without bends
• Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity
• Intersection of curves and crossing number of \(C_m\times C_n\) on surfaces
• Arrangements, circular arrangements and the crossing number of \(C_{7} \times C_{n}\).
• The crossing number of \(C(mk;\{1,k\})\)
• An improved bound for the crossing number of \(C_m\times C_n\): a self-contained proof using mostly combinatorial arguments
• Crossing number is hard for cubic graphs
• On the crossing numbers of loop networks and generalized Petersen graphs
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• [https://portal.mardi4nfdi.de/wiki/Publication:3156923 The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)]
• ON PLANARITY OF DIRECT PRODUCT OF MULTIPARTITE COMPLETE GRAPHS
• Universality considerations in VLSI circuits
• On the crossing numbers of products of cycles and graphs of order four
• Isomorphic components of Kronecker product of bipartite graphs
• The crossing number of c₄ × c₄
• Diagonal and toroidal mesh networks
• Doing the twist: diagonal meshes are isomorphic to twisted toroidal meshes
• An Upper Bound for the Bisection Width of a Diagonal Mesh
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Some crossing numbers of products of cycles
• The Categorical Product of Graphs

This page was built for publication: Orthogonal drawings and crossing numbers of the Kronecker product of two cycles