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

DOI10.1016/J.JPDC.2011.11.009zbMATH Open1242.68193OpenAlexW2094825239MaRDI QIDQ433407FDOQ433407

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

Kronecker productgraph algorithmscyclesgraph minorgridsCartesian productcrossing numbervertex partitionorthogonal drawing

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Independence in direct-product graphs
• The Categorical Product of Graphs
• Crossing number is hard for cubic graphs
• Title not available (Why is that?)
• On the computational complexity of upward and rectilinear planarity testing
• Universality considerations in VLSI circuits
• The crossing number of \(C(mk;\{1,k\})\)
• On the crossing numbers of loop networks and generalized Petersen graphs
• A framework for solving VLSI graph layout problems
• 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}\).
• An improved bound for the crossing number of \(C_m\times C_n\): a self-contained proof using mostly combinatorial arguments
• Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree
• Title not available (Why is that?)
• The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)
• ON PLANARITY OF DIRECT PRODUCT OF MULTIPARTITE COMPLETE GRAPHS
• 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
• Title not available (Why is that?)
• Some crossing numbers of products of cycles
• The crossing numbers of join of the special graph on six vertices with path and cycle

Cited In (5)

• Rotation and crossing numbers for join products
• On the crossing number for Kronecker product of a tripartite graph with path
• Cycle Kronecker products that are representable as optimal circulants
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)

   Recommendations

• Geometric drawings of \(K_{n}\) with few crossings 👍 👎
• The crossing numbers of certain Cartesian products 👍 👎
• Some crossing numbers of products of cycles 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Shellable drawings and the cylindrical crossing number of \(K_n\) 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433407)