Document:

<Page>

                                                                     Exhibit 4.1

[GRAPHIC]

<Table>
<S><C>
 COMMON STOCK                                                     COMMON STOCK

PAR VALUE $.001                                       THIS CERTIFICATE IS TRANSFERRABLE IN
                                                           NEW YORK, NY OR CHICAGO, IL

CERTIFICATE                       [NAVTEQ LOGO]                                SHARES
  NUMBER                                                             * * 6 0 0 6 2 0 * * * * * *
 ZQ 000220                                                           * * * 6 0 0 6 2 0 * * * * *
                                                                     * * * * 6 0 0 6 2 0 * * * *
                               NAVTEQ CORPORATION                    * * * * * 6 0 0 6 2 0 * * *
              INCORPORATED UNDER THE LAWS OF THE STATE OF DELAWARE   * * * * * * 6 0 0 6 2 0 * *

THIS CERTIFIES THAT        MR. SAMPLE & MRS. SAMPLE &               CUSIP 63936L 10 0
                            MR. SAMPLE & MRS. SAMPLE
                                                           SEE REVERSE FOR CERTAIN DEFINITIONS

is the owner of             * * * SIX HUNDRED THOUSAND
                           SIX HUNDRED AND TWENTY* * *
</Table>

           FULLY-PAID AND NON-ASSESSABLE SHARES OF THE COMMON STOCK OF

NAVTEQ CORPORATION (HEREINAFTER CALLED THE "COMPANY"), transferable on the books
of the Company in person or by duly authorized attorney, upon surrender of this
Certificate properly endorsed. This Certificate and the shares represented
hereby, are issued and shall be held subject to all of the provisions of the
Articles of Incorporation, as amended, and the By-Laws, as amended, of the
Company (copies of which are on file with the Company and with the Transfer
Agent), to all of which each holder, by acceptance hereof, assents. This
Certificate is not valid unless countersigned and registered by the Transfer
Agent and Registrar.

WITNESS the facsimile seal of the Company and the facsimile signatures of its
duly authorized officers.

<Table>
<S>                               <C>                  <C>
                                                       DATED [[Month Day, Year]]
/s/ Judson Green                     [SEAL]
    President                                          COUNTERSIGNED AND REGISTERED:
                                     NAVTEQ            COMPUTERSHARE INVESTOR SERVICES, LLC.
                                  INCORPORATED         (CHICAGO)
                                    DECEMBER           TRANSFER AGENT AND REGISTRAR,
                                       18
                                      1987
                                    DELAWARE
                                   CORPORATION

/s/ Lawrence M. Kaplan                                 By
   Secretary                                             ----------------------------
                                                             AUTHORIZED SIGNATURE
</Table>

                        SECURITY INSTRUCTIONS ON REVERSE
                                                                           14969

<Page>

The following abbreviations, when used in the inscription on the face of this
certificate, shall be construed as though they were written out in full
according to applicable laws or regulations:

<Table>
<S>                                         <C>
TEN COM -as tenants in common               UNIF GIFT MIN ACT- ..............Custodian...............
                                                                  (Cust)                  (Minor)
TEN ENT -as tenants by the entireties                       under Uniform Gifts to Minors Act...............
                                                                                                 (State)
JT TEN  -as joint tenants with right of     UNIF TRF MIN ACT ......................Custodian (until age...)...........
         survivorship and not as tenants                            (Cust)                                  (Minor)
         in common                                          under Uniform Transfers to Minors Act...............
                                                                                                     (State)
</Table>

        Additional abbreviations may also be used though not in the above list.

NAVTEQ CORPORATION

THE COMPANY WILL FURNISH WITHOUT CHARGE TO EACH STOCKHOLDER WHO SO REQUESTS, A
SUMMARY OF THE POWERS, DESIGNATIONS, PREFERENCES AND RELATIVE, PARTICIPATING,
OPTIONAL OR OTHER SPECIAL RIGHTS OF EACH CLASS OF STOCK OF THE COMPANY AND THE
QUALIFICATIONS, LIMITATIONS OR RESTRICTIONS OF SUCH PREFERENCES AND RIGHTS, AND
THE VARIATIONS IN RIGHTS, PREFERENCES AND LIMITATIONS DETERMINED FOR EACH
SERIES, WHICH ARE FIXED BY THE ARTICLES OF INCORPORATION OF THE COMPANY, AS
AMENDED, AND THE RESOLUTIONS OF THE BOARD OF DIRECTORS OF THE COMPANY, AND THE
AUTHORITY OF THE BOARD OF DIRECTORS TO DETERMINE VARIATIONS FOR FUTURE SERIES.
SUCH REQUEST MAY BE MADE TO THE OFFICE OF THE SECRETARY OF THE COMPANY OR TO THE
TRANSFER AGENT. THE BOARD OF DIRECTORS MAY REQUIRE THE OWNER OF A LOST OR
DESTROYED STOCK CERTIFICATE, OR HIS LEGAL REPRESENTATIVES, TO GIVE THE COMPANY A
BOND TO INDEMNIFY IT AND ITS TRANSFER AGENTS AND REGISTRARS AGAINST ANY CLAIM
THAT MAY BE MADE AGAINST THEM ON ACCOUNT OF THE ALLEGED LOSS OR DESTRUCTION OF
ANY SUCH CERTIFICATE.

For value received,_______________________hereby sell, assign and transfer unto

PLEASE INSERT SOCIAL SECURITY
OR OTHER IDENTIFYING NUMBER
OF ASSIGNEE                     _______________________________

________________________________________________________________________________
(PLEASE PRINT OR TYPEWRITE NAME AND ADDRESS, INCLUDING POSTAL ZIP CODE, OF
ASSIGNEE)

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________  Shares
of the capital stock represented by the within Certificate, and do hereby
irrevocably constitute and appoint

_______________________________________________________________________ Attorney
to transfer the said stock on the books of the within-named Corporation with
full power of substitution in the premises.

Dated:                20                 Signature:
      ----------------  -----                      -----------------------------

Signature(s) Guaranteed:                 Signature:
                                                   -----------------------------
BY:                                                Notice: THE SIGNATURE TO THIS
   ---------------------------                             ASSIGNMENT MUST
THE SIGNATURE(S) SHOULD BE                                 CORRESPOND WITH THE
GUARANTEED BY AN ELIGIBLE                                  NAME AS WRITTEN UPON
GUARANTOR INSTITUTION (Banks,                              THE FACE OF THE
Stockbrokers, Savings and Loan                             CERTIFICATE, IN EVERY
Associations and Credit                                    PARTICULAR, WITHOUT
Unions) WITH MEMBERSHIP IN AN                              ALTERATION OR
APPROVED SIGNATURE GUARANTEE                               ENLARGEMENT, OR ANY
MEDALLION PROGRAM, PURSUANT TO                             CHANGE WHATEVER.
S.E.C. RULE 17Ad-15.

[GRAPHIC]

SECURITY INSTRUCTIONS

THIS IS WATERMARKED PAPER, DO NOT ACCEPT WITHOUT NOTING
WATERMARK HOLD TO LIGHT TO VERIFY WATERMARK.<Page>

                                                                     Exhibit 4.6

                    AGREEMENT REGARDING REGISTRATION OF SHARES

     This AGREEMENT REGARDING REGISTRATION OF SHARES ("Agreement") is made as of
May 17, 2004 by and between NAVTEQ Corporation ("Company") and NavPart I B. V.
("Stockholder").

     WHEREAS, the Company has filed a registration statement on Form S-1
("Registration Statement") with the Securities and Exchange Commission under the
Securities Act of 1933, as amended, ("Act") to register the offer and sale of
certain shares of the Company's common stock, $0.001 par value, held by Philips
Consumer Electronic Services B. V. ("Philips") pursuant to a firm commitment
underwritten public offering ("Offering"); and

     WHEREAS, the Stockholder has requested that the Company register the offer
and sale under the Act certain shares of the Company's common stock it holds
("Stockholder Shares") by including such shares in the Registration Statement;
and

     WHEREAS, the Company has indicated its willingness to include such
Stockholder Shares in the Registration Statement, subject to the terms and
conditions specified in this Agreement.

     NOW, THEREFORE, in consideration of the mutual promises and covenants
contained herein, the parties agree as follows:

1.   AGREEMENT TO REGISTER SHARES. Subject to the conditions set forth herein,
the Company agrees to use its commercially reasonable efforts to register the
Stockholder Shares by including such shares in the Registration Statement. The
number of Stockholder Shares to be registered will be determined through
consultation with Credit Suisse First Boston LLC and Merrill Lynch & Co., the
Underwriters of the Offering. Such number of shares may be increased or
decreased at any time prior to the completion of the Offering in the sole
discretion of the Underwriters.

2.   CONDITIONS TO COMPANY'S OBLIGATION. In addition to the condition set forth
in Section 5 below, the obligations of the Company to include the Stockholder
Shares in the Registration Statement are expressly subject to the following
conditions:

     (a)  the Stockholder shall become a party to the Underwriting Agreement
between the Company, the Underwriters, Philips and the Stockholder;

     (b)  the Stockholder cooperates with the Company and the Underwriters as
requested by the Company and/or Underwriters in connection with the Registration
Statement and the Offering, including, without limitation, providing such
information as is requested by them for inclusion in the Registration Statement
and executing such agreements, acknowledgments and certificates as are customary
in transactions of this type;

     (c)  Philips consents to the inclusion of the Stockholder Shares in the
Registration Statement; and

<Page>

     (d)  the Registration Statement is not withdrawn and/or the Offering is not
completed for any reason.

3.   FEES AND EXPENSES. The Company shall be responsible for the Securities and
Exchange Commission, National Association of Securities Dealers, Inc., New York
Stock Exchange and "blue sky" law registration, qualification and compliance
fees and expenses in connection with the registration of the Stockholder Shares.
The Selling Stockholder shall be responsible for all underwriting discounts,
selling commissions and transfer taxes, if any, applicable to the sale of the
Stockholder Shares, and the fees and expenses of its counsel.

4.   NO OTHER REGISTRATION RIGHTS. The Stockholder acknowledges and agrees that
the Company's agreement to register the Stockholder Shares pursuant to this
Agreement does not create any further right of Stockholder to have any of its
shares registered in any subsequent registration of the offer and sale of
Company securities under the Act (whether in an offering by the Company or for
the account of any Company securityholder). The Stockholder further acknowledges
and agrees that nothing in this Agreement is intended to make the Stockholder a
party to or confer upon such Stockholder any rights set forth in that certain
Registration Rights Agreement dated as of March 29, 2001 by and between the
Company and Philips.

5.   AGREEMENT OF UNDERWRITERS. The obligations of the Company and the rights of
the Stockholder under this Agreement are expressly conditioned on the consent
and agreement of the Underwriters to include the Stockholder Shares in the
Offering. In the event that the Underwriters determine, in their sole
discretion, not to include the Stockholder Shares in the Offering, the Company's
obligations under this Agreement shall cease and be of no further force or
effect.

6.   REASONABLE INVESTIGATION. In connection with the preparation and filing of
the Registration Statement and the completion of the Offering, the Company will
provide the Stockholder reasonable and customary access to the Company's books
and records and such opportunities to discuss the business of the Company with
its officers as shall be reasonably necessary to conduct a reasonable
investigation within the meaning of the Act.

7.   NON-TRANSFERABILITY. The rights and obligations of the Stockholder under
this Agreement may not be transferred or assigned without the written agreement
of the Company.

8.   GOVERNING LAW. This Agreement and the rights and obligations of the parties
hereto shall be governed by and construed in accordance with the laws of the
state of Delaware, but not including the choice of law rules thereof.

9.   ENTIRE AGREEMENT. This Agreement constitutes the full and entire
understanding and agreement of the parties with regard to the subject matters
described herein and supersedes and any and all prior agreements and
understandings between the parties with regard to the subject matters described
herein. This Agreement may be amended or modified only by written agreement of
the parties.

                                        2
<Page>

10.  EXECUTION IN COUNTERPARTS. This Agreement may be executed in any number of
counterparts, each of which shall be an original, but all of which together
shall constitute one instrument.

         [remainder of page intentionally blank -signature page follows]

                                        3
<Page>

          [signature page - Agreement Regarding Registration Of Shares]

     IN WITNESS WHEREOF, the parties have executed this Agreement as of the date
first set forth above.

                                COMPANY:

                                NAVTEQ Corporation

                                By:      /s/ Judson C. Green
                                       --------------------------
                                       Judson C. Green
                                       President and Chief Executive Officer

                                STOCKHOLDER:

                                NavPart I B.V.

                                By:    /s/ Dirk-Jan van Omineren
                                       --------------------------
                                Name:  Dirk-Jan van Omineren
                                       --------------------------
                                Title:        Director
                                       --------------------------

                                        4

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00067-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00067-of-00352.parquet"}]]