Embedding linear orders in grids



: Ehrenfeucht A, Harju T, Rozenberg G

Publisher: SPRINGER

: 2006

 Acta Informatica

: ACTA INFORMATICA

: ACTA INFORM

: 42

: 6-7

: 419

: 428

: 10

: 0001-5903

DOI: https://doi.org/10.1007/s00236-005-0001-9


A grid (or a mesh) is a two-dimensional permutation: an m x n-grid of size mn is an m x n-matrix where the entries run through the elements {1,2, ..., mn}. We prove that if delta(1) and delta(2) are any two linear orders on {1,2,..., N}, then they can be simultaneously embedded (in a well defined sense) into a unique grid having the smallest size.



Last updated on 14/10/2025 09:55:31 AM